This innocence is brilliant.
LOJ3120 「CTS2019」珍珠
有一个 n 个数的序列，每一个数在 $1 \dotsc D $中随机生成，定义一个序列是合法的当且仅当能取出至少 m 个对子（相同的数），对于$ D^n $种可能的序列，求合法序列数。$D \leq 10^5, n, m \leq 10^9$。
题解
感觉生成函数其实自己什么都不会。。。。草还是抄题解
先特判掉 $n \leq 2m $和 $d \leq (n - 2m + 1) $的情况，分别应当输出 0 和 $D^n$。(Pigeonhole principle)
令 $\{di\} $表示 $i$ 这个数在 $a{1 \dotsc n}$ 中出现了几次。那么假设能够取出 $m $对，则 $\displaystyle (\sum{i=1}^D d_i \bmod 2) \leq (n - 2m)$。考虑枚举 $\displaystyle m = \sum{i=1}^D di \bmod 2$，令 $\displaystyle F(x) = \sum{i=0}^\infty [i \bmod 2 = 1] \frac {x^i} {i!}, G(x) = \sum_{i=0}^\infty [i \bmod 2 = 0] \frac {x^i} {i!} $，
记 $[x^n]f(x)$ 表示幂级数 $f$ 的 $n$ 次项系数.用生成函数化简得：
$ans = \sum_{k=0}^{n-2m} \binom {D} {k} n! [x^n] F^i(x) G^{D-k}(x)$
考虑到$ \displaystyle F(x) = \frac {e^x - e^{-x}} {2}, G(x) = \frac {e^x + e^{-x}} {2}$ （这里是查表还是推的啊qwq？），代入并二项式定理展开
$\begin{aligned}
ans = \frac 1 {2^D} \sum{k=0}^{n-2m} \sum{i=0}^k \sum{j=0}^{D-k} [x^n] n! (-1)^{k-i} \binom D k \binom k i \binom {D-k} j e^{x(2i + 2j - D)} \\
= \frac 1 {2^D} \sum{k=0}^{n-2m} \sum{i=0}^k \sum{j=0}^{D-k} (-1)^{k-i} \binom D k \binom k i \binom {D-k} j (2i + 2j - D)^n \\
= \frac {D!} {2^D} \sum{k=0}^{n-2m} \sum{i=0}^k \sum_{j=0}^{D-k} \frac {(-1)^{k-i} (2i + 2j - D)^n} {i! (k-i)! j! (D-k-j)!} \\
\end{aligned}$
这样直接做就是$ \mathcal O(D ^ 3) $的了虽然变形一下式子前缀和搞一搞可以优化到 $\mathcal O(D ^2)$
对于上面这个式子，我们发现除了$ (-1)^{k-i}$ 以外都与 $i $和 $j$ 具体的值无关，只和 $i + j $有关。我们稍微变形一下式子：
$ans = \frac {D!} {2^D} \sum{k=0}^{n-2m} \sum{i+j=0}^{D} \frac {(2(i+j)-D)^n} {(i+j)! (D-i-j)!} \sum_{i=0}^k \frac {(i+j)!} {i! j!} \cdot \frac {(D-i-j)!} {(k-i)! (D-k-j)!} (-1)^{k-i}$
考虑$ \displaystyle \frac {(x+y)!} {x! y!} = \binom {x+y} x $的组合意义即从 $(0, 0) $出发，每次可以向下或向右走一步（即 (+1, 0) 和 (0, +1) ），最后到达 $(x, y)$ 的方案数。
那么式子就转化为从$ (0, 0) $走到 $(i, j) $，再从$ (i, j)$ 走到 (k, D - k)，其中一种方案的权值为$ (-1)^{k-i}$，要求所有方案的权值和。显然我们可以直接从 (0, 0) 走到 $(k, D - k)$。
用一个生成函数来解决「走路」的过程，还是不考虑 $(-1)^{k-i}$，则应当形如
$[x^k] (1+x)^D$
考虑把$ (-1)^{k-i} $放进去，那么
$\begin{aligned}
ans
= \frac {D!} {2^D} \sum{i=0}^D \frac {(2i-D)^n} {i! (D-i)!} \sum{k=0}^{n-2m} [x^k] (1+x)^i (1-x)^{D-i} \\
= \frac {1} {2^D} \sum{i=0}^D (2i-D)^n \binom Di \sum{k=0}^{n-2m} [x^k] (1+x)^i (1-x)^{D-i}
\end{aligned}$
假设
$F(i, D) = \sum_{k=0}^{n-2m}[x^k] (1+x)^i (1-x)^{D-i}$
那么
$ans = \frac 1 {2^D} \sum_{i=0}^{D} (2i-D)^n \binom D i F(i, D)$
也就是说我们需要求得 $F(0 \dotsc n, D) $，考虑递推
$F(0, 0) = 1$
$\begin{aligned}
F(0, D)
= \sum{k=0}^{n-2m} [x^k] (1-x)^D \\
= \sum{k=0}^{n-2m} (-1)^k \binom D k \\
= \sum{k=0}^{n-2m} (-1)^k \left( \binom {D-1} k + \binom {D-1} {k-1} \right) \\
= \left( \sum{k=0}^{n-2m} (-1)^k \binom {D-1} k \right) + \left( \sum_{k=0}^{n-2m-1} (-1)^k \binom {D-1} k \right) \\
= (-1)^{n-2m} \binom {D-1} {n-2m}
\end{aligned}$
$\begin{aligned}
F(i, D)
= \sum{k=0}^{n-2m} [x^k] (1+x)^i (1-x)^{D-i} \\
= \sum{k=0}^{n-2m} [x^k] (-(1-x) + 2) (1+x)^{i-1} (1-x)^{D-i} \\
= \sum_{k=0}^{n-2m} [x^k] -\left( (1+x)^{i-1} (1-x)^{D-i+1} \right) + 2\left( 2(1+x)^{i-1} (1-x)^{D-i}\right) \\
= -F(i - 1, D) + 2 F(i - 1, D - 1)
\end{aligned}$
那么又回到了之前走格子的问题上，我们可以从 $(0, 1 \dotsc D)$ 中的任何一个点出发并携带 $F(0, 1 \dotsc D) $的权值。每次可以有两种移动方式，第一种 $(+1, 0) $并使得携带的值乘上 -1，第二种$ (+1, +1) $并使得携带的值乘上 2。可以发现每走一步 x 坐标一定会 +1，那么就是从 i 步选了 $\Delta y = D - j $步走了 $(+1, +1)$。
$\begin{aligned}
F(i, D) = \sum_{j=0}^{D} F(0, j) (-1)^{i+j-D} 2^{D-j} \binom i {D-j}
\end{aligned}$
那么
$\begin{aligned}
ans
= \frac 1 {2^D} \sum{i=0}^D (2i-D)^n \binom D i F(i, D) \\
= \frac 1 {2^D} \sum{i=0}^D (2i-D)^n \binom D i \sum{j=0}^D F(0, j) (-1)^{i+j-D} 2^{D-j} \binom i {D-j} \\
= \frac {(-1)^D D!} {2^D} \sum{i=0}^D \sum_{j=0}^D \frac {1} {(i + j - D)!} \cdot \frac {(2i - D)^n} {(D-i)!} \cdot \frac {2^{D-j} F(0, j)} {(D-j)!}
\end{aligned}$
设
$\begin{aligned}
f(x) = \sum{i=0}^D \frac {(2i - D)^n x^i} {(D-i)!} \\
g(x) = \sum{i=0}^D \frac {2^{D-j} F(0, i)x^i} {(D-i)!}
\end{aligned}$
这样就可以得到
$ans = \frac 1 {2^D} \sum_{k=D}^{2D} \frac { [x^k] \left( f(x) \cdot g(x) \right) } {(-1)^k (k-D)!}$
直接 NTT 即可。