题解 P6151 【[集训队作业2019] 青春猪头少年不会梦到兔女郎学姐】

· · 题解

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 ，对于一种排列方式，贡献可以如下计算：先把这个序列首尾相连，然后把所有相邻且颜色相同的段拿出来，贡献为他们的长度之积，求所有贡献和。

$\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)。

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