P6031 CF1278F Cards 加强版解题报告

解题报告

---

P6031 CF1278F Cards 加强版解题报告：

更差的阅读体验

题意

$m$张牌，有一张是王牌，打乱$n$次，设有$x$次第一次为王牌，求$x^k$的期望。（$1\leqslant n,m<998244353,1\leqslant k\leqslant 10^7$）

分析

死亡推式子题。。。刚好可以总结一些推式子题套路。

设$p=\frac{1}{m}$，那么首先很容易列出式子：

$$\sum_{i=0}^n{n\choose i}p^i(1-p)^{n-i}i^k$$

$i$枚举王牌出现次数，然后不难得到这个式子。

但这个和式的上界是$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^m=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}{n\choose i}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}$$

这个结论很常见：

$${n\choose i}{i\choose k}=\frac{n!i!}{i!k!(n-i)!(i-k)!}\cdot\frac{(n-k)!}{(n-k)!}\\=\frac{n!}{k!(n-k)!}\cdot\frac{(n-k)!}{(i-k)!(n-i)!}={n\choose k}{n-k\choose i-k}$$

利用上面提到的第二类斯特林数通项暴力展开，再次交换求和式：

$$=\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$$

对上面展开幂次的式子二项式反演得：

$$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m{m\choose i}(-1)^{m-i}i^n$$

设$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;
}