题解 P6031【CF1278F Cards 加强版】
whiteqwq
·
·
题解
P6031 CF1278F Cards 加强版解题报告：
更好的阅读体验
题意
## 分析
死亡推式子题。。。刚好可以总结一些推式子题套路。
设$p=\frac{1}{m}$，那么首先很容易列出式子（$i$枚举王牌出现次数）：
$$\sum_{i=0}^n{n\choose i}p^i(1-p)^{n-i}i^k$$
但这个和式的上界是$n$，怎么优化枚举都没有办法，所以套路地用第二类斯特林数展开，然后交换求和式（组合意义就是$m$个球放到$n$个盒子里）：
$$
=\sum_{i=0}^n{n\choose i}p^i(1-p)^{n-i}\sum_{j=0}^i\begin{Bmatrix}k\\j\end{Bmatrix}{i\choose j}j!
$$
$$
=\sum_{j=0}^n j!\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=j}^n{n\choose i}{i\choose j}p^i(1-p)^{n-i}
$$
然后利用一个结论${n\choose i}{i\choose k}={n\choose k}{n-k\choose i-k}$（下方有说明）继续推：
$$
=\sum_{j=0}^nj!\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=j}^n{n\choose j}{n-j\choose i-j}p^i(1-p)^{n-i}
$$
$$
=\sum_{j=0}^nj!\begin{Bmatrix}k\\j\end{Bmatrix}{n\choose j}\sum_{i=0}^{n-j}{n-j\choose i}p^{i+j}(1-p)^{n-i-j}
$$
$$
=\sum_{j=0}^nj!\begin{Bmatrix}k\\j\end{Bmatrix}{n\choose j}p^j\sum_{i=0}^{n-j}{n-j\choose i}p^i(1-p)^{(p-j)-i}
$$
$$
=\sum_{j=0}^nj!\begin{Bmatrix}k\\j\end{Bmatrix}{n\choose j}p^j(1-p+p)^{n-j}=\sum_{j=0}^kj!p^j{n\choose j}\begin{Bmatrix}k\\j\end{Bmatrix}$$
利用上面提到的第二类斯特林数通项暴力展开，再次交换求和式：
$$
=\sum_{j=0}^kj!p^j{n\choose j}\frac{1}{j!}\sum_{i=0}^j{j\choose i}(-1)^{j-i}i^k
$$
$$
=\sum_{i=0}^ki^k\sum_{j=i}^k{n\choose j}{j\choose i}p^j(-1)^{j-i}
$$
$$
=\sum_{i=0}^k (-1)^ki^k{n\choose i}\sum_{j=i}^n{n-i\choose j-i}(-p)^j
$$
$$
=\sum_{i=0}^k(-1)^ki^k{n\choose i}\sum_{j=0}^{k-i}{n-i\choose j}(-p)^{j+i}
$$
$$=\sum_{i=0}^kp^ii^k{n\choose i}\sum_{j=0}^{k-i}{n-i\choose j}(-p)^j$$
设$S(i)=\sum_{j=0}^{k-i}{n-i\choose j}(-p)^j$，那么原式就变成可以$O(k)$递推的式子了：
$$=\sum_{i=0}^kp^ii^k{n\choose i}S(i)$$
那么我们现在就要求出$S(1\cdots k)$，很容易知道$i=k$时$S(i)=1$。
考虑倒序递推$S(i)$，直接暴力展开组合数：
$$
S(i)=\sum_{j=0}^{k-i}{n-i\choose j}(-p)^j
$$
$$
=\sum_{j=0}^{k-i}({n-i-1\choose j}+{n-i-1\choose j-1})(-p)^j
$$
$$
=\sum_{j=0}^{k-i}{n-(i+1)\choose j}(-p)^j+\sum_{j=0}^{k-i}{n-i-1\choose j-1}(-p)^j
$$
$$
=S(i+1)+{n-i-1\choose k-i}(-p)^{k-i}+(-p)\sum_{j=0}^{k-(i+1)}{n-(i+1)\choose j}(-p)^j
$$
$$=(1-p)S(i+1)+{n-i-1\choose k-i}(-p)^{k-i}$$
那么我们随便筛一下，然后拆一下组合数，就可以线性递推出来$S(1\cdots k)$了。
## 代码
谨慎起见，可以特判一下$n<k$的情况。
```
#include<stdio.h>
const int maxk=10000005,mod=998244353;
int n,m,k,p,cnt,ans,mul;
int pw[maxk],c[maxk],P[maxk],inv[maxk],S[maxk],pmul[maxk],npmul[maxk],fmul[2];
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)
res=1ll*res*a%mod;
a=1ll*a*a%mod,b>>=1;
}
return res;
}
void sieve(int n){
fmul[0]=1,fmul[1]=mod-1;
inv[1]=c[1]=pw[1]=1;
for(int i=2;i<=n;i++){
inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
if(c[i]==0)
P[++cnt]=i,pw[i]=ksm(i,k);
for(int j=1;j<=cnt;j++){
if(i*P[j]>n)
break;
c[i*P[j]]=1,pw[i*P[j]]=1ll*pw[i]*pw[P[j]]%mod;
if(i%P[j]==0)
break;
}
}
pmul[0]=npmul[0]=1;
for(int i=1;i<=n;i++)
pmul[i]=1ll*pmul[i-1]*p%mod,npmul[i]=1ll*npmul[i-1]*(1-p+mod)%mod;
}
int main(){
scanf("%d%d%d",&n,&m,&k),p=ksm(m,mod-2);
sieve(k);
if(n<k){
mul=1;//C(n,0)
for(int i=0;i<=n;i++){
ans=(ans+1ll*mul*pmul[i]%mod*npmul[n-i]%mod*pw[i]%mod)%mod;
mul=1ll*mul*inv[i+1]%mod*(n-i)%mod;//C(n,i)->C(n,i+1)
}
printf("%d\n",ans);
return 0;
}
S[k]=1;
mul=n-k;//C(n-k,1)
for(int i=k-1;i>=0;i--){
S[i]=(1ll*(1-p+mod)*S[i+1]%mod+1ll*mul*fmul[(k-i)&1]%mod*pmul[k-i]%mod)%mod;
mul=1ll*mul*inv[k-i+1]%mod*(n-i)%mod;//C(n-i-1,k-i)->C(n-i,k-i+1)
}
mul=1;//C(n,0)
for(int i=0;i<=k;i++){
ans=(ans+1ll*pmul[i]*pw[i]%mod*mul%mod*S[i]%mod)%mod;
mul=1ll*mul*inv[i+1]%mod*(n-i)%mod;//C(n,i)-C(n,i+1)
}
printf("%d\n",ans);
return 0;
}
```