Atcoder abc260
https://atcoder.jp/contests/abc260/tasks
Ex - Colorfulness
n球, 颜色ci
f(球的一个排列) = 相邻不同色的个数
对于k=1..m分别求 $\sum(f(排列)^k)$ mod 998244353
范围
n 2.5e5
m 2.5e5
ci [1,n]
8s
1024mb
我的思路
k==1 时
那颜色可以分开考虑
一个颜色 去计算它能构成x个间隔, 那么它每个贡献 (x+1(两端))/2, 再乘上方案数
注意每个排列的最左和最右还要-1, 所以还要减 n!
k==2时
明显就不一样了, 因为贡献变成了 (相邻不同色)^2
颜色c 有 x间隔 ( (x+1) + 其它颜色间隔贡献 -1)^2
问题 其它颜色贡献会受到颜色c的间隔数x 影响
如果直接按照题目来, 按f(P)归类
如果能算出 不同为y个的 出现次数t(y)
那么 就是 f(1) = sum t(y) * y
f(2) = sum t(y) * y^2
这样做也是 需要O(n m) 的
而且怎么算不同出现次数也没啥想法
题解
注意到如果只看颜色的话, 一个方案 对应的实际排列 总是乘上 所有颜色个数的阶乘的积, 所以可以把这个 颜色个数的阶乘的积 提出来, 看成没有差别的同色小球
也是先计算$t_i =$ 有多少个排列会有i个不同的相邻颜色
然后再基于t 计算 和
计算排列出现次数
直接算$t$有点难, 先定义两个序列p,q
pi= 指定i个相邻同颜色(未指定的异色) 的排列数
qi= 指定i个相邻同颜色(未指定的任意) 的排列数, 注意这里不是>=i个, 比如 1=2=3 在指定1个相邻想等时, 1=2里会被统计一次, 2=3里也会被统计一次,
显然 $t_i = p_{N-1-i}$
有 $q_n = \sum_{k=n}^{N-1} \binom{k}{n} p_k$
根据容斥/二项式反演, 有
$p_n = \sum_{k=n}^{N-1} (-1)^{k-n} \binom{k}{n} q_k$
可以卷积O(n log n) , abc272里有(虽然在260后面, 但我先补的272
所以如何计算q
$m_i$ 为第$i$种颜色的个数
$k_i$ 为第$i$种颜色指定的 相邻相同的个数
$a_{c,k} = \binom{m_c-1}{k}$ 颜色c中指定了k个
$q_n = \sum_{k_1, k_2, \dots, k_N ,\sum_{c} k_c = n} \left(\binom{N-n}{m_1-k_1, m_2-k_2, \dots, m_N-k_N}\prod_{c} a_{c,k_c} \right) = (N-n)! \sum_{k_1, k_2, \dots, k_N ,\sum_{c} k_c = n} \prod_{c} \frac{a_{c,k_c}}{(m_c-k_c)!}$
那么指定后,如果把相邻的看成不可变顺序的多个整体, 那么就是 $N-n$个位置中 放置$m_i-k_i$ 个不可变顺序的整体 !!!! 这样就不会不同颜色之间有影响了!!! (之前因为一个颜色是否连会影像空隙个数, 从而影响其它颜色的空隙个数), 这是上面公式的 左边binom
右边就是每个颜色内, $m_c-1$个相邻位置指定$k_c$个, 这里要注意的是, 可能有的颜色为0个, 这种不会出现在c里,
看到 是prod的sum, 每个prod 只和$c$有关, 那么就是生成函数的方向
用$r_i$对它颠倒 $r_i = q_{N-i}$, 有$r_0=q_N=0$
$r_n = n! \sum_{k_1, k_2, \dots, k_N ,\sum_{c} k_c = n} \prod_{c} \frac{a_{c,m_c-k_c}}{k_c!}$
这里$n$的意义变了, 我觉得用 $\mathrm{new} k_i = m_i- \mathrm{old} k_i$ 看起来变化更自然
注意到$k_c$原来 的范围是$[0,m_c-1]$, 现在变成$[1,m_c]$, 注意到如果$\mathrm{new} k_c \equiv 0$ 那么对应是不合法情况 $\frac{a_{c,m_c}}{k_c!} = \frac{\binom{m_c-1}{m_c}}{k_c!}$ , 方便起见, 令$a_{m-1,m} = 0$ 即可, 所以$k_c$的值域范围变成$[0,m_c]$
做生成函数 $g_c(x) = \sum_{k=0}^{m_c} \frac{a_{c,m_c-k}}{k!} x^k,$
那么$r_n = n! \times [x^n] \prod_{c} g_c(x).$
所以 右侧直接 分治计算生成方程, 可以O(n log n) 算出
至此,$t_i$ 可以算出
n次方带系数和
方程到很直接, 显然$F(n) = \sum_{k=0}^{N-1} k^n t_k.$
现在子问题就是 给定$N$和序列$t$, 求 $F(1\cdots 2.5\cdot10^5)$
把$F(n)$看成生成方程的系数
$\begin{aligned} &f(x) \\ &=\sum_{n=0}^\infty F(n) x^n \\ &=\sum_{n=0}^\infty \left( \sum_{k=0}^{N-1} k^n a_k \right) x^n \\ &=\sum_{k=0}^{N-1} a_k \left( \sum_{n=0}^\infty (kx)^n\right) \\ &=\sum_{k=0}^{N-1} \left(\frac{a_k}{1-kx}\right). \end{aligned}$
之前遇到过乘积拆和的$\frac{c}{(1-x)(1-2x)\cdots}$, 这里是和变乘积, 需要搞一个 $f(x) = \frac{s(x)}{t(x)}$,
同样分治搞一搞 就可以得到$s$和$t$了
好家伙, abc272 我自己找资料学了如何算 生成函数的 倒数, 看来还是应该按照顺序补题, 这里题解里竟然还有教学
然后 变成$s(x) \cdot t^{-1}(x)$ 即可
总结
这场现场过了A-F, 赛后超时过了G, 就Ex不会
Ex
好像第二次遇到二项式反演, 虽然也是容斥的一部分, 但感觉 这种等于变成 大于等于 或者小于等于的转化 还是可以抽出一个类别
不过第一部分的计算, 应该已经都是学过的知识了没有新知识, 虽然只学了一两次, 还是不熟
然后这里 其实要求那么多值 反而很明显应该向 $F$看成系数去想, 然后球和换元的那里感觉是个我的瓶颈 没想到
参考
/algo/Newton_s_method