【题解】魔术卡排列问题（相邻相同对计数）

一、问题抽象

我们有 $m$ 种颜色的卡片，第 $i$ 种颜色有 $a_i$ 张，总张数 $\sum_{i=1}^m a_i = n$。 将它们排成长度为 $n$ 的序列，称相邻两张颜色相同的位置为一个魔术对。 求恰好有 $k$ 个魔术对的排列方案数，答案对 $998244353$ 取模。

注意：相同颜色的卡片是不可区分的，只有颜色种类不同才视为不同。

---

二、核心转化

2.1 从“相邻相同对数”到“连续段数”

设颜色 $i$ 的 $a_i$ 张卡片在排列中被分成 $b_i$ 个连续段（每个段内颜色相同，不同段之间可能相邻也可能不相邻）。
例如：AABBA 中颜色 A 有 $a_A=3$ 张，被分成 $b_A=2$ 段（AA 和 A）。

重要关系：

• 颜色 $i$ 内部，分成 $b_i$ 段会产生 $(a_i - b_i)$ 个段内相邻相同对（因为每段长度减 1 就是该段的相邻对）。
• 总相邻相同对数：$$k = \sum_{i=1}^m (a_i - b_i) = n - \sum_{i=1}^m b_i $$
• 设总段数 $B = \sum_{i=1}^m b_i$，则：$$B = n - k$$ 且 $1 \le b_i \le a_i$（每种颜色至少一段，最多所有卡连续成一段）。

---

2.2 问题分解

对于一组满足 $\sum b_i = B$ 且 $1 \le b_i \le a_i$ 的 $(b_1,\dots,b_m)$，方案数由两部分相乘：

1. 分块方案数：对于颜色 $i$，将 $a_i$ 张卡分成 $b_i$ 个非空连续段的方法数 = $\binom{a_i-1}{b_i-1}$（插板法）。
2. 块排列方案数：将 $b_1$ 个颜色 $1$ 的块、$b_2$ 个颜色 $2$ 的块、……、$b_m$ 个颜色 $m$ 的块排成一行，使得相邻块颜色不同的排列数。记此数为 $F(b_1,\dots,b_m)$。

于是总方案数：

$$\text{Ans} = \sum_{\substack{b_1+\dots+b_m = B \\ 1 \le b_i \le a_i}} \left[ \prod_{i=1}^m \binom{a_i-1}{b_i-1} \right] \cdot F(b_1,\dots,b_m) $$

---

三、计算 $F(b_1,\dots,b_m)$

这是已知各颜色球的数量，排成一列，相邻颜色不同的方案数。

3.1 插入 DP 方法

定义 $dp[i][s]$ = 考虑前 $i$ 种颜色，已经放置了 $s$ 个块，且满足相邻不同的方案数。
转移：当加入第 $i$ 种颜色的 $b$ 个块时，这些块之间不能相邻（因为颜色相同），所以必须插入到已有的 $s$ 个块形成的 $s+1$ 个空隙中，且每个空隙最多放一个新块。
插入方法数 = $\binom{s+1}{b}$（从 $s+1$ 个空隙中选 $b$ 个放入新块）。

转移方程：

$$dp[i][s+b] \ += dp[i-1][s] \cdot \binom{a_i-1}{b-1} \cdot \binom{s+1}{b} $$

初始 $dp[0][0]=1$，最终 $dp[m][B]$ 就是答案。

复杂度：$O(m B \cdot \max a_i)$，无法通过大数据。

---

3.2 容斥原理方法（更高效）

设 $g(t)$ = 至少有 $t$ 个魔术对的方案数。
“至少 $t$ 个魔术对”等价于“总段数 $B \le n-t$ 且相邻块可以同色”。
更准确地说，至少有 $t$ 个魔术对时，我们可以把这些相邻相同对“合并”，得到 $n-t$ 个块，但合并后的块之间可能同色也可能不同。

直接计算 $g(t)$ 的一种方法：

• 将 $a_i$ 张卡分成 $b_i$ 个块，总块数 $B = n-t$。
• 不考虑相邻块是否同色，排列这些块的方法数为 $\frac{B!}{\prod b_i!}$（因为同色块不可区分）。
• 因此：$$g(t) = \sum_{\substack{b_1+\dots+b_m = n-t \\ 1 \le b_i \le a_i}} \left[ \prod_{i=1}^m \binom{a_i-1}{b_i-1} \right] \cdot \frac{(n-t)!}{\prod_{i=1}^m b_i!} $$

---

3.3 从 $g(t)$ 得到 $f(k)$

设 $f(k)$ = 恰好 $k$ 个魔术对的方案数。
“至少有 $t$ 个魔术对” = 在 $k \ge t$ 的排列中，任选 $t$ 个魔术对作为“指定”的。所以：

$$g(t) = \sum_{k=t}^{n-1} \binom{k}{t} f(k)$$

由二项式反演：

$$f(k) = \sum_{t=k}^{n-1} (-1)^{t-k} \binom{t}{k} g(t) $$

---

四、多项式优化

4.1 计算 $g(t)$ 的生成函数

令 $B = n-t$，则：

$$g(t) = (n-t)! \cdot \sum_{\substack{b_1+\dots+b_m = B \\ 1 \le b_i \le a_i}} \prod_{i=1}^m \frac{\binom{a_i-1}{b_i-1}}{b_i!} $$

定义：

$$h(B) = \sum_{\substack{b_1+\dots+b_m = B \\ 1 \le b_i \le a_i}} \prod_{i=1}^m \frac{\binom{a_i-1}{b_i-1}}{b_i!} $$

则 $g(t) = (n-t)! \cdot h(n-t)$。

构造多项式：

$$H_i(x) = \sum_{b=1}^{a_i} \frac{\binom{a_i-1}{b-1}}{b!} x^b $$

那么：

$$\prod_{i=1}^m H_i(x) = \sum_{B \ge m} h(B) x^B$$

4.2 算法步骤

1. 预处理阶乘和组合数，用于计算 $\binom{a_i-1}{b-1}$ 和 $\frac{1}{b!}$。
2. 分治 NTT 计算多项式乘积 $H(x) = \prod_{i=1}^m H_i(x)$，得到系数 $h(B)$。
3. 计算 $g(t) = (n-t)! \cdot h(n-t)$（$t=0,1,\dots,n-1$）。
4. 二项式反演：$$f(k) = \sum_{t=k}^{n-1} (-1)^{t-k} \binom{t}{k} g(t) $$这也等价于一个卷积： 令 $A_t = g(t) \cdot t!$，$C_{t-k} = \frac{(-1)^{t-k}}{(t-k)!}$，则：$$f(k) \cdot k! = \sum_{t=k}^{n-1} A_t \cdot \frac{(-1)^{t-k}}{(t-k)!} $$即 $f(k) \cdot k! = (A * C)[k]$，用 NTT 卷积计算。
5. 输出 $f(k)$。

---

五、复杂度分析

• 构造每个 $H_i(x)$：$O(a_i)$。
• 分治 NTT 计算总乘积：$O(n \log n \log m)$。
• 卷积计算二项式反演：$O(n \log n)$。
• 总复杂度：$O(n \log n \log m)$，可满足 $n \le 10^5$。

---

六、关键点总结

1. 核心转化：相邻相同对数 $k$ → 总段数 $B = n-k$。
2. 分块计数：每种颜色分成 $b_i$ 段的方案数用组合数表示。
3. 相邻不同排列：转化为容斥或生成函数问题。
4. 多项式优化：利用 NTT 加速多项式乘法，处理大数据范围。
5. 二项式反演：从“至少”方案数得到“恰好”方案数。

这种方法充分利用了模数 $998244353$ 支持 NTT 的特性，是本题的最优解法。