纪念第一个场切的 EDU 的 F。
题意：
有 \(n\) 个不同的盒子，每个盒子里有 \(m\) 个编号分别为 \(1\dots m\) 的小球。现在要从每个盒子中恰好取出 \(1\) 个球，计算每种取法中，编号是奇数的小球个数的 \(k\) 次方和，答案对 \(998244353\) 取模。
首先，我们设 \(a\) 为 \(1 \dots m\) 中奇数的个数，\(b\) 为 \(1 \dots m\) 中偶数的个数
显然，对于编号是奇数的小球个数相等的取法，其贡献是等价的。
考虑生成函数，设 \(F=(ax+b)^{n}\)，则我们要求的答案就是：
\[\sum_{i=1}^{n} [x^i] F \times i^k \]因为由二项式定理，有：
\[F=\sum_{i=1}^{n} \binom{n}{i}a^{i}b^{n-i}x^i \]所以 \([x^i]F=\binom{n}{i}a^{i}b^{n-i}\)。
于是得出：
\[ans=\sum_{i=1}^{n} \binom{n}{i}a^{i}b^{n-i} i^k \]然后我们发现这个东西和 CF932E Team Work 非常相似，于是我们仿照那题的套路来处理。
\[\begin{aligned}ans &=\sum_{i=1}^{n} \binom{n}{i}a^{i}b^{n-i} i^k \\ & = \sum_{i=1}^{n} \binom{n}{i}a^{i}b^{n-i} \sum_{j=1}^{k}\begin{Bmatrix} k \\ j \end{Bmatrix} i^{\underline{j}}\\ & = \sum_{i=1}^{n} \binom{n}{i}a^{i}b^{n-i} \sum_{j=1}^{k}\begin{Bmatrix} k \\ j \end{Bmatrix} \binom{i}{j} j! \end{aligned} \]改变求和顺序：
\[\begin{aligned} & = \sum_{j=1}^{k}\begin{Bmatrix} k \\ j \end{Bmatrix} j!\sum_{i=1}^{n} \binom{n}{i} \binom{i}{j} a^{i}b^{n-i} \\ & = \sum_{j=1}^{k}\begin{Bmatrix} k \\ j \end{Bmatrix} j!\sum_{i=1}^{n} \binom{n}{i} \binom{i}{j} a^{i}b^{n-i} \\ & = \sum_{j=1}^{k}\begin{Bmatrix} k \\ j \end{Bmatrix} j!\sum_{i=1}^{n} \binom{n}{j} \binom{n-j}{i-j} a^{i}b^{n-i} \\ & = \sum_{j=1}^{k}\begin{Bmatrix} k \\ j \end{Bmatrix} \binom{n}{j} j!\sum_{i=1}^{n} \binom{n-j}{i-j} a^{i}b^{n-i} \\& = \sum_{j=1}^{k}\begin{Bmatrix} k \\ j \end{Bmatrix} n^{\underline{j}} \sum_{i=1}^{n} \binom{n-j}{i-j} a^{i}b^{n-i} \end{aligned} \]前面的循环已经可以求解了，现在考虑后半部分：
\[\begin{aligned} \sum_{i=1}^{n} \binom{n-j}{i-j} a^{i}b^{n-i} \end{aligned} \]考虑到 \(i < j\) 时 $ \binom{n-i}{i-j} =0$，不会产生贡献，于是可以重写为：
\[\begin{aligned} \sum_{i=j}^{n} \binom{n-j}{i-j} a^{i}b^{n-i} \end{aligned} \]等价于：
\[\begin{aligned} &=\sum_{i=0}^{n-j} \binom{n-j}{i} a^{i+j}b^{n-i-j} \\ &= a^{j} \sum_{i=0}^{n-j} \binom{n-j}{i} a^{i} b^{n-j-i} \\ &= a^j (a+b)^{n-j} \end{aligned} \]于是我们最终的式子可以写成：
\[\sum_{j=1}^{k}\begin{Bmatrix} k \\ j \end{Bmatrix} n^{\underline{j}} a^j (a+b)^{n-j} \]第二类斯特林数可以用 \(O(k^2)\) 的预处理递推出来，\(n\) 的下降幂也可以 \(O(k)\) 预处理。于是这道题就能用 \(O(k^2+Tk)\) 的复杂度完成了。
标签：Bags,begin,Balls,end,sum,aligned,Bmatrix,binom,CF1716F From： https://www.cnblogs.com/jimmywang/p/16637530.html