Luogu5401 珍珠
题意：有 \(n\) 个变量，取值范围均为 \([1,D]\) 中的整数。求有多少种取值方案，使得可以选出至少 \(m\) 对变量满足每对都相等。
\(1\le D\le 10^5,\space 0\le m\le n,\space 1\le n\le 10^9\)
注意到 \(D\) 很小，我们可以计算出个数为奇数的值最多 \(n-2m\) 个，偶数最少为 \(t=\max(0,D-n+2m)\)。设 \(g[i]\) 表示恰好 \(i\) 个值出现偶数次的方案数。
二项式反演，设 \(f[i]\) 表示钦定 \(i\) 个值出现偶数次的方案数。
因为是有标号算多重集，所以使用 EGF。对于每个值，钦定出现次数为偶数的 EGF 为 \(\sum\limits_{i=0} \dfrac{x^i+(-x)^i}{2i!}=\dfrac{e^x+e^{-x}}2\)，不钦定的 EGF 为 \(e^x\)。
那么
\[\begin{aligned} f[k] &= {D \choose k} [x^n](\frac{e^x+e^{-x}}2)^k * (e^x)^{D-k} \\ &= {D \choose k} \frac 1{2^k} [x^n] (e^x+e^{-x})^k * e^{(D-k)x} \\ &= {D \choose k} \frac 1{2^k} [x^n] \sum_{i=0}^k {k \choose i} e^{ix} * e^{(i-k)x} * e^{(D-k)x} \\ &= {D \choose k} \frac 1{2^k} [x^n] \sum_{i=0}^k {k \choose i} e^{(D+2i-2k)x} \\ &= {D \choose k} \frac 1{2^k} \sum_{i=0}^k {k \choose i} (D+2i-2k)^n \\ &= {D \choose k} \frac {k!}{2^k} \sum_{i=0}^k \frac {(D+2i-2k)^n}{i!} \cdot \frac 1{(k-i)!} \end{aligned} \]直接 NTT，二项式反演用差卷积，时间 \(O(D(\log D+\log n))\)。
标签：练习题,le,frac,sum,2i,2024.3,choose,EGF From： https://www.cnblogs.com/Sktn0089/p/18057764