有 \(n\) 个在范围 \([1,D]\) 内的整数均匀随机变量。
求至少能选出 \(m\) 个瓶子，使得存在一种方案，选择一些变量，并把选出来的每一个变量放到一个瓶子中，满足每个瓶子都恰好装两个值相同的变量的概率。
请输出概率乘上 \(D^n\) 后对 \(998244353\) 取模的值。取模部分说明可参考 。
\(0\le m\le 10^9,1\le n\le 10^9,1\le D\le 10^5\) 。
\(FFT\) ，生成函数
对于 \(2m>n\) 和 \(n-2m \ge D\) 的情况先特判掉。
不难发现，设 \(a_i\) 为颜色 \(i\) 出现的次数，我们要求的就是能满足 \(\sum a_i\ mod\ 2 \le n - 2m\) 的方案数。
设 \(f_i\) 为恰好有 \(i\) 种颜色出现次数为奇数的方案数，则有：
写出 \(f_i\) 的表达式之后不太好求，我们需要令限制更少一点。
考虑钦定 \(i\) 个颜色的出现次数为奇数，设 \(h_i\) 为，对于钦定的某 \(i\) 种颜色，使得出现次数为奇数，且其他颜色出现次数随意的方案数。
设 \(g_i = \tbinom{D}{i} h_i\) ，也就是对于每种不同的钦定方案，我们将其求和。
那么根据定义，必然有等式：
因为每个 \(f_j\) 都会被 \(g_i\) 中的 \(\tbinom{j}{i}\) 种钦定方案算到。
利用指数形生成函数 \(\sum c^n\frac{x^i}{i!} = e^{cx}\) 可得：
随后因为 \([x^n]e^{cx}=\frac{c^n}{n!}\) ，直接代入得：
这样就可以卷积了。
然后根据定义式直接算出 \(\{g_i\}\) 。
根据二项式反演可得：
设 \(p_{D-j-i}=g_{j+i}(j+i)!\)，则有：
这样就可以卷积了。
原文：https://www.cnblogs.com/luoshuitianyi/p/12852875.html