[洛谷P5401][CTS2019]珍珠

感觉这个题挺有意思的,直接推式子就完事了。
用x的次数表示珠子个数,y的次数表示落单的珠子个数,由题意可值,只要落单的珠子个数不超过n-m-m即为合法,不妨令$k=min(n-m-m,D)$
那么题目的生成函数为:
$$n!\Big( \displaystyle\sum_{i=0}^{\infty} \big( \frac{x^{2i}}{(2i)!}+\frac{x^{2i+1}y}{(2i+1)!}\big) \Big)^D$$
$$=n!\Big(\frac{e^x+e^{-x}}{2}+\frac{e^x-e^{-x}}{2}y\Big)^D$$
$$=\frac{n!}{2^D}\Big( e^x(1+y)+e^{-x}(1-y)\Big)$$
$$=\frac{n!}{2^D}\displaystyle\sum_{i=0}^D e^{(2i-D)x} (1+y)^i (1-y)^{D-i} \binom{D}{i}$$
取$\lbrack x^n\rbrack$这一项得到:
$$\frac{1}{2^D}\displaystyle\sum_{i=0}^D (2i-D)^n (1+y)^i (1-y)^{D-i} \binom{D}{i}$$
我们现在要求所有y次数不超过k的系数之和,那么等价于该多项式乘上$\frac{1}{1-y}$之后求系数为k的这一项之和。也就是说,答案为:
$$\Big( \frac{1}{2^D} \displaystyle\sum_{i=0}^D (2i-D)^n (1+y)^i (1-y)^{D-i-1} \binom{D}{i}\Big)\lbrack y^k \rbrack$$
$$=\frac{1}{2^D}\Big( \Big( \displaystyle\sum_{i=0}^{D-1} (2i-D)^n \displaystyle\sum_{j=0}^i \binom{i}{j} \binom{D-i-1}{k-j} \binom{D}{i} (-1)^{k-j} \Big)+\Big( \displaystyle\sum_{j=0}^k D^n \binom{D}{j} \Big) \Big)$$
前面部分FFT优化,后面部分暴力,总复杂度$\Theta(D(\lg D+\lg n))$
代码:

Tagged with:

发表评论