考虑序列上的问题。
首先考虑枚举数字 \(i\) 划分为 \(a_i\) 段，所有方案的权值之和为 \(\binom{c_i+a_i-1}{2a_i-1}\)。
这不难通过组合意义证明：权值可以视作将 \(c_i\) 个数字划分为 \(a_i\) 段，再在每一段中选择一个的方案数。
那么这些数字段之间的顺序安排的方案数，即有 \(a_i\) 个数字 \(i\)，相同数字不得相邻的多重集排列数。
对于数字 \(i\)，\(a_i\) 之间没有顺序影响，于是不相邻的限制可以看做 \(a_i-1\) 对数字 \(i\) 不得相邻的限制。
考虑容斥，枚举 \(b_i\) 表示打破多少限制，那么相当于数字 \(i\) 被强制缩为 \(a_i-b_i\) 个段，有 \[
\sum\limits_{0\le b_i \le a_i-1} \prod\limits_{i=1}^n (-1)^{b_i} \binom{a_i-1}{b_i} \frac{[\sum_{i=1}^n (a_i-b_i)]!}{(a_i-b_i)!}
\]
综合 \(a_i\) 的枚举，并改为枚举 \(d_i=a_i-b_i\)，可得 \[ \begin{aligned} & \sum\limits_{1 \le a_i \le c_i} \sum\limits_{1 \le d_i \le a_i} \left(\sum\limits_{i=1}^n d_i\right)! \prod\limits_{i=1}^n \binom{c_i+a_i-1}{2a_i-1} (-1)^{a_i-d_i} \frac{(a_i-1)!}{(a_i-d_i)!(d_i-1)d_i!} \\ =& \sum\limits_{1 \le d_i \le c_i} \left(\sum\limits_{i=1}^n d_i\right)! \sum\limits_{d_i \le a_i \le c_i} \prod\limits_{i=1}^n (-1)^{a_i-d_i} \binom{c_i+a_i-1}{2a_i-1} \frac{(a_i-1)!}{(a_i-d_i)!(d_i-1)!d_i!} \end{aligned} \]
考虑构造生成函数以通过卷积关于 \(c_i\) 之和统计答案。 \[ \begin{aligned} F_i(x) &= \sum\limits_{j=1}^{c_i} \frac{x^j}{(j-1)!j!} \sum\limits_{k=j}^{c_i} \binom{c_i+k-1}{2k-1} (-1)^{k-j} \frac{(k-1)!}{(k-j)!} \\ &= \sum\limits_{j=1}^{c_i} \frac{x^j}{(j-1)!j!} \sum\limits_{k=0}^{c_i-j} \binom{c_i+(j+k)-1}{2(j+k)-1}(j+k-1)! \cdot (-1)^{k} \frac1{k!} \end{aligned} \]
不难构造卷积求出生成函数，再执行分治 NTT 即可。
再考虑环上的问题。可以强制使开头为 \(1\)，结尾不为 \(1\)，即开头为 \(1\) 的减去开头结尾均为 \(1\) 的。
分别相当于强制安排了 \(1,2\) 段数字 \(1\) 的位置，可以对 \(F_1(x)\) 左移来实现（注意左移不包括那个 \(\frac1{j!}\)，因为强制确定了顺序）。
然后循环移位也要计算贡献，故乘上 \(\sum\limits_{i=1}^n c_i\)。
然而这样 \(i\) 段 \(1\) 的序列会被计算 \(i\) 次。在 \(F_1(x)\) 中乘上 \(\frac1{a_1}\) 即可。
代码：
1 |
|