某模拟 T2 小丑做法

· · 个人记录

题意：问有多少个序列满足：长度为 n ；1\le a_i\le m；不存在 l_1<l_2<r_1<r_2 使得 a_{l_1}=a_{r_1}=x,a_{l_2}=a_{r_2}=y 且 x\neq y 。n\le 10^9,m\le 10^6 。

记 f_{n,m} 表示：长度为 n ，且 1 到 m 中每种权值都出现了的序列个数，则答案为 \sum\limits_{i=0}^m f_{n,i}\tbinom{m}{i} 。

设 F(x,y)=\sum f_{n,m}x^ny^m ，则我们有 F=xyF+xF^2-xF+1 。解得 F=\frac{-(xy-x-1)+\sqrt{(xy-x-1)^2-4x}}{2x} 。

考虑用广义二项式定理展开这个根号，即 ((xy-x-1)^2-4x)^{\frac{1}{2}}=\sum\limits_{i\geq 0} \frac{(-4x)^i(1*(-1)*(-3)*\dots*(3-2i))(xy-x-1)(xy-x-1)^{-i}}{2^ii!} 。化简一下，\sum\limits_{i\geq 1} \frac{-2x^i(2i-2)!(xy-x-1)(xy-x-1)^{-i}}{i!(i-1)!} 。我们要计算 \frac{1}{2}[x^{n+1}y^m]\sum\limits_{i\geq 1} \frac{-2x^i(2i-2)!(xy-x-1)(xy-x-1)^{-i}}{i!(i-1)!} 。经过展开，化简等简单操作，n:=n+1 ，我们最后能把式子写成：\frac{(n-1)!}{(n-m)!}\sum\limits_{i=1}^{n-m} (-1)^{n-m-i}\tbinom{n+i-2}{i-1}\tbinom{n-m}{i} 。

昨天到这里我就以为化不动了，但今天我发现，你考虑后面这个式子的组合意义，相当于有 n-m 个盒子，钦定 n-m-i 个为空，然后把 n-1 个球放入剩下 i 个盒子里，可空。这不就是在算 n-1 个球放入 n-m 个盒子且不能为空吗？？于是整个都等于 \tbinom{n-2}{n-m-1} 了。

总结一下，答案即为 \sum\limits_{i\geq 1}\tbinom{m}{i}\frac{n!}{(n+1-i)!}\tbinom{n-1}{n-i} 。容易 O(m) 计算。