自动搬运

查看原文

来自洛谷，原作者为

	iostream Think three times, code twice and take the first place.

搬运于2025-08-24 22:17:57，当前版本为作者最后更新于2020-03-01 15:37:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

5.7 update ：现在公式似乎不会出锅了？

引例：$n$ 种颜色的球分别 $a_i$ 个，相邻不同色，排列，方案数。

$m=\sum a_i\le 10^5$

首先考虑题目中的限制条件是什么，对于单种颜色的球从左往右看，第 $i$ 个跟第 $i+1$ 个不相邻，那么该颜色就对应着 $a_i-1$ 个限制。

普通容斥，也就是枚举打破多少限制

$$\sum_{b_1\sim b_n,b_i\in[0,a_i-1]} \prod_{i=1}^n(-1)^{b_i}{a_i-1\choose b_i}\times {(\sum a_i-b_i)!\over \prod_{i=1}^n (a_i-b_i)!} $$

换成枚举 $c_i=a_i-b_i$，然后 $c_i$ 的意义是说第 $i$ 个颜色强制缩成这么多个段。

$$\sum_{c_1\sim c_n,c_i\in [1,a_i]} (\sum c_i)!\prod_{i=1}^n(-1)^{a_i-c_i}{(a_i-1)!\over (a_i-c_i)!(c_i-1)!}{1\over c_i!} $$

注意到可以按 $\sum c_i$ 统计答案，那么构造关于后式的普通生成函数

$$F_i(x)=\sum_{j=1}^{a_i}(-1)^{a_i-j}{(a_i-1)!\over (a_i-j)!(j-1)!j!}x^j $$

用分治 ntt 卷积以后统计答案即可，复杂度 $O(m\log^2m)$。

当然这个是带标号球的拼接，显然可以直接用指数生成函数来理解，本质是一样的。

回到本题

给定 $n$ 种颜色的球，第 $i$ 种颜色的球数量为 $r_i$ ，对于一种排列方式，贡献可以如下计算：先把这个序列首尾相连，然后把所有相邻且颜色相同的段拿出来，贡献为他们的长度之积，求所有贡献和。 $(1,2,1,2)$ 和 $(2,1,2,1)$ 贡献相同但排列方式不同，要分别计算。

$\sum r_i\le 2\times 10^5$

我们首先考虑不成环的情况。

Step 1

枚举把颜色 $i$ 切成 $a_i$ 段，设 $f(x,y)$ 表示 $x$ 有序的切成 $y$ 段的所有方案，每段长度乘积之和。

问题转换为交错排列，直接套用上题的式子，那么有：

$$\sum_{a_1\sim a_n,a_i\in[1,r_i]}f(r_i,a_i)\sum_{c_1\sim c_n,c_i\in [1,a_i]} (\sum c_i)!\prod_{i=1}^n(-1)^{a_i-c_i}{(a_i-1)!\over (a_i-c_i)!(c_i-1)!}{1\over c_i!} $$

把 $c_i$ 整到前面来得到

$$\sum_{c_1\sim c_n,c_i\in [1,r_i]} (\sum c_i)!\sum_{c_i\le a_i\le r_i}f(r_i,a_i)\prod_{i=1}^n(-1)^{a_i-c_i}{(a_i-1)!\over (a_i-c_i)!(c_i-1)!}{1\over c_i!} $$

那么维护生成函数

$$F_i(x)=\sum_{j=1}^{r_i}\sum_{j\le a_i\le r_i}f(r_i,a_i)(-1)^{a_i-j}{(a_i-1)!\over (a_i-j)!(j-1)!j!}x^j $$

Step 2

考虑算这个 $F_i(x)$ 有 $f(x,y)={x+y-1\choose 2y-1}$ ，可以结合组合意义理解，考虑插板出一个方案，对于每一个连续段还要选出一个位置，相当于 $x+y-1$ 个位置选出 $2y-1$ 个位置。

于是计算 $F_i(x)$ 是一个卷积形式。

Step 3

分治 ntt 计算每种球的生成函数的乘积，复杂度 $O(m\log^2 m)$。

Step 4

要做环上的情况，我们钦定颜色 1 在序列最前头并且结尾不是 1，那么用开头是 1 的 - 开头结尾都是 1 的。

（钦定 $t$ 个位置为 1 相当于把 $F_1(x)$ 多项式往左平移 $t$ 位。）

这样的一种方案，我们可以通过任意旋转的方式遍历所有可行方案，那么我们最终把答案乘以 $m=\sum r_i$ 即可。

Step 5

然后你发现这样会算重，具体的，一个方案有 $j$ 段颜色 1，会被每个 1 遍历一遍，所以算重 $j$ 遍，那么可以在颜色 1 的生成函数中带上 $1\over j$ 的系数来抵消掉，问题才最终解决。

另外一种未知原理的方法

考虑计算关于序列的生成函数 $f(x)$, 则 $ans=m\sum_{j=1}^m (j-1)![x^j]f(x)$。

目前我不太清楚为什么，知道原理的大佬请评论区留言或者私信，谢谢！