[Educational Round 133][Codeforces 1716F. Bags with Balls]

更好的阅读体验

给自己的 cnblogs 博客引路

一道很好的第二类斯特林数题，当然如果不会相关知识却知道函数求导的话，也可以推出公式（本人就属于后者）。

PS：不过 OIer 如果会函数求导的话应该肯定会斯特林数吧……

题目链接：1716F - Bags with Balls

题目大意：设一个长度为 n，元素取值在 [1,m] 内的数组 A 中的奇数元素个数为 x。令 F(A)=x^k，对所有可能的 A，求 \sum F(A)。

首先肯定是列式子，设奇数个数为 x，偶数个数为 y。那么枚举奇数个数，就有：

ans=\sum_{i=1}^{n}i^k\cdot C_n^i\cdot x^iy^{n-i}

关于式子的简化有两种做法，下面一一介绍。

做法一（函数求导）

这是本人考场上想到的做法，需要对初等函数求导有基础的了解，适合不熟悉第二类斯特林数的选手，如果觉得太长可以看简单粗暴的做法二。

考虑组合数学中恒等式 \sum_{i=1}^n i\cdot C_n^i=n\cdot2^{n-1} 及 \sum_{i=1}^n i^2\cdot C_n^i=n(n+1)\cdot2^{n-2} 的证明过程，先看第一个式子：

• 设 f(x)=(1+x)^n=\sum_{i=0}^{n} C_n^i\cdot x^i，将函数关于 x 求导；
• 得到 n\cdot (1+x)^{n-1}=\sum_{i=1}^ni\cdot C_n^i\cdot x^{i-1}；
• 两边同乘 x 得 n\cdot x(1+x)^{n-1}=\sum_{i=1}^ni\cdot C_n^i\cdot x^{i}；
• 将 x=1 代入即可得，n\cdot 2^{n-1}=\sum_{i=1}^n i\cdot C_n^i。

对于第二个式子，我们也可以利用同样的技巧：

• 首先还是得到 n\cdot x(1+x)^{n-1}=\sum_{i=1}^ni\cdot C_n^i\cdot x^{i}；
• 还是关于 x 求导得到 n\cdot (1+x)^{n-1}+n(n-1)\cdot x(1+x)^{n-2}=\sum_{i=1}^ni^2\cdot C_n^i\cdot x^{i-1}；
• 同样再次乘 x：n\cdot x(1+x)^{n-1}+n(n-1)\cdot x^2(1+x)^{n-2}=\sum_{i=1}^ni^2\cdot C_n^i\cdot x^{i}；
• 再次将 x=1 代入就是 n(n+1)\cdot2^{n-2}=\sum_{i=1}^n i^2\cdot C_n^i。

通过上述两个式子的证明过程，我们不难发现，每次我们只要将式子 \sum_{i=1}^ni^k\cdot C_n^i\cdot x^{i} 求导后再乘以 x，就能得到式子 \sum_{i=1}^ni^{k+1}\cdot C_n^i\cdot x^{i}。但是我们需要求的式子是 \sum_{i=1}^{n}i^k\cdot C_n^i\cdot x^iy^{n-i}，那么只需要把一开始的函数变成 f(x)=(x+y)^n，并把 y 看成一个已知常数，就能够得到对应的式子了，那么我们只需要求出等式左边每一项的系数就可以做到 O(k) 的快速求解。另外如果有大佬熟练掌握生成函数求导应该也有其它的解题方法，但是由于本弱不会所以我们来另辟蹊径。

我们设 f(x)=(x+y)^n，再走一遍刚刚的流程：

• ……

那么到这里我们可以发现，等式左边与 x 有关的式子都是 x^i(x+y)^{n-i} 的形式，而对应的系数则是一个数字乘上一个 n 的下降幂，即 \frac{n!}{(n-i)!}=n^{\underline{i}}，我们来关注一下经过 k 次求导后，x^i(x+y)^{n-i} 的系数 c(k,i) 的递推式。

对于 x^i(x+y)^{n-i}，我们将其求导后可以得到 i\cdot x^{i-1}(x+y)+(n-i)\cdot x^{i}(x+y)^{n-i-1}。那么乘以 x 后就能得到 i\cdot x^{i}(x+y)+(n-i)\cdot x^{i+1}(x+y)^{n-i-1}，由此可以得出 c(k,i) 对 c(k+1,i) 和 c(k+1,i+1) 分别有 i 和 n-i 的贡献。于是就有递推式 c(k,i)=i\cdot c(k-1,i)+(n-i+1)\cdot c(k-1,i-1)。

那么可以通过（打表）观察得出，若设 c(k,i)=s(k,i)\cdot n^{\underline{i}}，就会有递推式 s(k,i)=i\cdot s(k-1,i)+s(k-1,i-1)。有了递推式之后就是预处理系数接一个 for 循环解决的事，实际上如果对第二类斯特林数有一定了解的话就不难看出这其实就是第二类斯特林数的递推式，不过就算不知道相关知识也不影响解题了。

最后把答案式子写出来（不要忘记 x+y=m）：

ans=\sum_{i=1}^{k}s(k,i)\cdot n^{\underline i}\cdot x^im^{n-i}

做法二（暴力推式子）

学弟的做法，比较简单粗暴，非常适合 OI 巨佬及具体数学带师，需要知道式子 n^m =\sum_{k=0}^m{m \brace k} \binom{n}{k}k!。{m \brace k} 即为第二类斯特林数 {S2}(m,k)。

\begin{aligned} ans& =\sum_{i=0}^{n}i^k\cdot \binom{n}{i}\cdot x^iy^{n-i}\\ & =\sum_{i=0}^{n}\binom{n}{i} x^iy^{n-i}\cdot \sum_{j=0}^k \begin{Bmatrix} k\\j \end{Bmatrix} \binom{i}{j}j!\\ & = \sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix} \sum_{i=0}^{n} \frac{n!}{i!(n-i)!}\cdot x^iy^{n-i}\cdot \frac{i!}{(i-j)!} \\ & = \sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix} \sum_{i=0}^{n} \frac{n!}{(n-i)!(i-j)!}\cdot x^iy^{n-i}\\ & = \sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix} \frac{n!}{(n-j)!}\sum_{i=0}^{n}\binom{n-j}{n-i} x^iy^{n-i}\\ & = \sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix} \frac{n!}{(n-j)!}\sum_{t=0}^{n-j}\binom{n-j}{t} x^{n-t}y^{t}\\ & = \sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix} n^{\underline j}\sum_{t=0}^{n-j}\binom{n-j}{t} x^j\cdot x^{n-j-t}y^{t}\\ & = \sum_{j=0}^{k}\begin{Bmatrix} k\\j \end{Bmatrix} n^{\underline j}x^jm^{n-j} \end{aligned}

也得到了一样的结果。

最后附上本人简短而又丑陋的代码，时间复杂度 O(k^2+Tk)，不要忘了 k 要和 n 取 \min：

#include<bits/stdc++.h>
using namespace std;
#define N 2020
#define LL long long
#define MOD 998244353
LL T,n,m,k,s[N][N];
LL qow(LL x,LL y){return y?(y&1?x*qow(x,y-1)%MOD:qow(x*x%MOD,y/2)):1;}
int main()
{
    s[1][1]=1;
    for(LL i=2;i<N;i++)
    for(LL j=1;j<=i;j++)
        s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%MOD;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld",&n,&m,&k);
        LL ans=0,x=m-m/2,inv=qow(m,MOD-2);
        for(LL i=1,K=x*qow(m,n-1)%MOD*n%MOD;i<=min(n,k);i++,K=K*x%MOD*inv%MOD*(n-i+1)%MOD)
            ans=(ans+s[k][i]*K)%MOD;
        printf("%lld\n",ans);
    }
}