Binomial sums 小练习 2|P6031 CF1278F Cards 加强版

· · 题解

P6031 CF1278F Cards 加强版

斯特林数被我杀死了。

感觉 analysis 大佬的那个 binomial sums 做法稍微复杂了点，所以我这里分享了个简单点的 binomial sums 做法。

答案式子列出来是容易的，显然每次王牌出现在第一个的概率是 p=\frac{1}{m}。

\sum\limits_{i=0}^{n}\binom{n}{i}p^i(1-p)^{n-i}i^k

然后你意识到这不就是 P6667 [清华集训2016] 如何优雅地求和？其中 f(i)=i^k 的点值容易线性筛出的，然后套那个题的 binomial sums 做法就完了。

求 \sum\limits_{i=0}^{n}f(i)\binom{n}{i}a^{i}(1-a)^{n-i}，给了 m 次多项式 f(x) 的 0\sim m 的点值。

首先对于 a=0/1 或 m\leq n 这些 corner cases 都是可以容易直接求的先求了。

给了点值，相当于给咱们 b_{X}=\sum\limits_{i=0}^{m} f_{i} [\frac{x^{i}}{i!}](e^{x})^{X}，求：

\sum\limits_{j=0}^mf_{j}[\frac{x^j}{j!}]\sum\limits_{i=0}^{n}\binom{n}{i}a^{i}(1-a)^{n-i}e^{ix}

可以构造出 F(x)=(ax+(1-a))^n，需要进行截断。

直接上 ODE！还是设 \mathbb F(x+1)=F(x+1)\bmod x^{m+1}，显然根据 binomial sums 的结论我们的答案就是 \sum\limits_{i=0}^{m}b_i[x^i]\mathbb F(x)。

\begin{aligned} anF(x)-(ax-a+1)F'(x)&=0\\ anF(x+1)-(ax+1)F'(x+1)&=0\\ an\mathbb F(x+1)-(ax+1)\mathbb F'(x+1)&=(an-am)x^m[x^m]F(x+1)\\ an\mathbb F(x)-(ax-a+1)\mathbb F'(x)&=(an-am)\binom{n}{m}a^m(x-1)^m\\ (an-ai)f_{i}+(a-1)(i+1)f_{i+1}&=(an-am)\binom{n}{m}\binom{m}{i}a^m(-1)^{m-i} \end{aligned}

然后做完了，时间复杂度 O(m)。

放回本题就是 O(k) 啦！

code：

const int N=1e7+100,mod=998244353;
int n,m,k,fac[N],ifac[N],inv[N];
LL ksm(LL a,LL b){
    LL res=1;for(;b;b>>=1,a=a*a%mod) if(b&1) res=res*a%mod;return res;
}
LL C(int n,int m){
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int pri[N],tot,pw[N];
bool vis[N];
void sieve(){
    pw[1]=1;
    rep(i,2,k){
        if(!vis[i]) pri[++tot]=i,pw[i]=ksm(i,k);
        for(int j=1;j<=tot&&i*pri[j]<=k;++i){
            vis[i*pri[j]]=1;
            pw[i*pri[j]]=1ll*pw[i]*pw[pri[j]]%mod;
            if(i%pri[j]==0) break;
        }
    }
}
bool _ED;
signed main(){
    fprintf(stderr,"%.20lf MB\n",(&_ST-&_ED)/1048576.0);
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(n,m,k),m=ksm(m,mod-2);
    if(m==1) return write(ksm(n,k),'\n'),0;
    sieve();
    fac[0]=1;
    rep(i,1,k) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[k]=ksm(fac[k],mod-2);
    per(i,k-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
    if(n<=k){
        LL ans=0,iv=ksm((mod+1-m)%mod,mod-2),mul=ksm((mod+1-m)%mod,n)*iv%mod*m%mod;
        rep(i,1,n) ans=(ans+C(n,i)*mul%mod*pw[i])%mod,mul=mul*iv%mod*m%mod;
        write(ans,'\n');return 0;
    }
    LL tmp=ksm(m,k+1)*(n-k)%mod*ifac[k]%mod,ans=0;
    inv[0]=1;
    rep(i,1,k) inv[i]=1ll*inv[i-1]*(n-i)%mod,tmp=tmp*(n-i+1)%mod;
    LL INV=ksm(inv[k],mod-2),f=0,ip=ksm(m,mod-2);
    per(i,k,1) {
        inv[i]=1ll*inv[i-1]*INV%mod,INV=INV*(n-i)%mod;
        LL res=tmp*C(k,i)%mod;
        if((k-i)&1) res=mod-res;
        res=(res+1ll*(mod+1-m)*(i+1)%mod*f)%mod;
        f=res*ip%mod*inv[i]%mod;
        ans=(ans+f*pw[i])%mod;
    }
    write(ans,'\n');
    fprintf(stderr,"%.4lf s\n",1.0*clock()/CLOCKS_PER_SEC);
    return 0;
}