【题解】CTS2019珍珠(二项式反演+卷积)

╰半夏微凉° 2021-11-18 01:22 267阅读 0赞

## 【题解】CTS2019珍珠 ##

题目就是要满足这样一个条件\\(c\_i\\)代表出现次数  
\\\[ \\sum \{\[\\dfrac \{c\_i \} 2\]\} \\ge 2m \\\]  
显然\\(\\sum c\_i=n\\)所以，而且假如\\(c\_i\\)是\\(2\\)的约数就有正常的贡献，如果不是就有少一点的贡献，那么  
\\\[ \\sum^D\_\{i=1\} \{\[2\\mid c\_i\]\} > n-2m \\\]  
设\\(f\_i\\)为钦定有\\(i\\)种颜色出现偶数次的方案。问题瞬间就变成了HAOI染色...

则有  
\\\[ f\_i=\{D\\choose i\}\[x^n\]n!(\\dfrac \{e^x+e ^\{-x\}\}\{2\})^i\{(e^x)\}^\{D-i\} \\\]  
选出钦定的\\(i\\)个颜色，后面是序列的生成方式。  
\\\[ 2^if\_i=\{D\\choose i\}\[x^n\]n!( \{e^x+e ^\{-x\}\})^i\{(e^x)\}^\{D-i\} \\\]  
展开\\(^i\\)  
\\\[ 2^if\_i=\{D\\choose i\}\[x^n\]n!\\sum\_\{j=0\}^i\{i\\choose j\}\{(e^x)\}^\{D+2j-2i\} \\\]  
由于是求\\(\[x^n\]\\)所以  
\\\[ 2^if\_i=\{D\\choose i\}n!\\sum\_\{j=0\}^i\{i\\choose j\}\\dfrac \{ \{(D+2j-2i)\}^n\}\{n!\} \\\]

\\\[ =\{D\\choose i\}\\sum\_\{j=0\}^i\{i\\choose j\} \{ \{(D+2j-2i)\}^n\} \\\]

所以  
\\\[ \\dfrac \{2^if\_i\}\{ \{D\\choose i\}i!\}=\\sum\_\{j=0\}^i \\dfrac \{(-(2i-2j-D))^n\}\{j!(i-j)!\} \\\]  
右边的式子直接NTT得到。

然而我们知道，这样的钦定是有重复的，具体如何重复参考\[【题解】[HAOI2018\]染色(NTT+容斥/二项式反演)][HAOI2018_NTT]。我们直接二项式反演:

设\\(g\_i\\)表示恰好\\(i\\)种颜色出现次数为偶数的方案，则考虑一下\\(g\_j\\)在\\(f\_i\\)出现的次数  
\\\[ f\_i=\\sum\_\{j=i\}^D \{j\\choose i\}g\_i \\\]  
直接二项式反演  
\\\[ g\_i=\\sum\_\{j=i\}^D (-1)^\{j-i\}\{j\\choose i\}f\_j \\\]  
下标从0没问题，变一下：  
\\\[ g\_i=\\sum\_\{j=0\}^D (-1)^\{j-i\}\\dfrac \{j!\}\{i!(j-i)!\}f\_j \\\]  
整理  
\\\[ \\dfrac \{g\_i\}\{i!\}=\\sum\_\{j=0\}^D \\dfrac\{(-1)^\{j-i\}\\times j!f\_j\}\{(j-i)!\} \\\]  
reverse一下，右边又直接NTT

最终答案：  
\\\[ \\sum\_\{i=n-2m+1\}^D g\_i \\\]  
你觉得肯定做不了，\\(n\\le 1e9\\)啊，但是考虑一些边界情况：

*  \\(n <2m\\)答案为0
 *  \\(n-2m+1>D\\)答案为\\(D^n\\)

所以如果用多项式算法的条件是  
\\\[ n\\ge2m\\\\n-2m+1\\le D=1e5\\\\ \\\]  
多项式的maxn开\\(1<<18\\)就行了。

代码真的懒得写就是套套板子调调参。

转载于:https://www.cnblogs.com/winlere/p/11247179.html

[HAOI2018_NTT]: https://www.cnblogs.com/winlere/p/11183570.html