题解：AT_abc458_e [ABC458E] Count 123

· · 题解

场上很多高手用组合意义秒了这题，但是我太菜了不会组合意义，所以我只能用代数推导啦。

我们首先先只填 2，然后不难发现一个事实：目前形成了 x_2+1 个空位，其中可以填任意个同种的 1 或 3 或不填，设 m=x_2+1，j,k 分别为 1 和 3 占用的空位的个数，其余不填。

不难使用插板法写出公式 ans=\sum_{j=1}^{x_1}\sum_{k=1}^{x_3}\binom{m}{j+k}\binom{j+k}{j}\binom{x_1-1}{j-1}\binom{x_3-1}{k-1}，但是这个东西显然是 O(n^2) 的，无法通过。

因为我很菜，所以我接下来只能暴力推导：\sum_{j=1}^{x_1}\sum_{k=1}^{x_3}\binom{m}{j+k}\binom{j+k}{j}\binom{x_1-1}{j-1}\binom{x_3-1}{k-1}=\sum_{j=1}^{x_1}\sum_{k=1}^{x_3}\frac{m!}{(j+k)!(m-(j+k))!}\frac{(j+k)!}{j!k!}\binom{x_1-1}{j-1}\binom{x_3-1}{k-1}=\sum_{j=1}^{x_1}\sum_{k=1}^{x_3}\frac{m!}{(m-(j+k))!}\frac{1}{j!}\frac{1}{k!}\binom{x_1-1}{j-1}\binom{x_3-1}{k-1}，到这里，我们将这些内容分成了三部分：与 j 相关的，与 k 相关的，与 j+k 相关的。

然后我们不难想到，将与 j 相关的和与 k 相关的分别视为两个多项式，求出两个多项式卷积后再对对应的位置乘上与 j+k 相关的项。利用 NTT 可以做到 O(n \log n)，做完了。

代码：https://www.luogu.com.cn/paste/0d57mwu3