题解 P5395 【第二类斯特林数·行】

· · 题解

众所周知，第二类斯特林数有性质：

m^n=\sum_{i=0}^m \binom m i \left\{ \begin{matrix} n \\ i \end{matrix} \right\} i!

然后可以愉快地二项式反演了。

设

f(m)=m^n,g(m)= \left\{ \begin{matrix} n \\ m \end{matrix} \right\}m!

那么就有

f(m)=\sum_{i=0}^m \binom{m}{i}g(i) \Leftarrow\Rightarrow g(m)=\sum_{i=0}^m \binom{m}{i}(-1)^{m-i}f(i)=\sum_{i=0}^m\binom m i(-1)^{m-i} i^n

于是就有

\left\{ \begin{matrix} n \\ m \end{matrix} \right\}m!=\sum_{i=0}^m \binom m i (-1)^{m-i} i^n \left\{ \begin{matrix} n \\ m \end{matrix} \right\}=\sum_{i=0}^m \frac{\binom m i (-1)^{m-i}i^n}{m!}

把组合数拆开来，就有：

\left\{ \begin{matrix} n\\m \end{matrix} \right\}=\sum_{i=0}^m \frac{i^n}{i!} \frac{(-1)^{m-i}}{(m-i)!}

发现这显然就是一个卷积形式，NTT 碾过去即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
const ll mod=167772161;
int G=3,invG;
const int N=2400000;
ll ksm(ll b,int n){
    ll res=1;
    while(n){
        if(n&1) res=res*b%mod;
        b=b*b%mod; n>>=1;
    }
    return res;
}
int tr[N];
void NTT(ll *f,int n,int fl){
    for(int i=0;i<n;++i)
        if(i<tr[i]) swap(f[i],f[tr[i]]);
    for(int p=2;p<=n;p<<=1){
        int len=(p>>1);
        ll w=ksm((fl==0)?G:invG,(mod-1)/p);
        for(int st=0;st<n;st+=p){
            ll buf=1,tmp;
            for(int i=st;i<st+len;++i)
                tmp=buf*f[i+len]%mod,
                f[i+len]=(f[i]-tmp+mod)%mod,
                f[i]=(f[i]+tmp)%mod,
                buf=buf*w%mod;
        }
    }
    if(fl==1){
        ll invN=ksm(n,mod-2);
        for(int i=0;i<n;++i)
            f[i]=(f[i]*invN)%mod;
    }
}
ll f[N],g[N],a[N],b[N],fac[N],inv[N];
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=0;--i)
        inv[i]=1ll*(i+1)*inv[i+1]%mod;
}
signed main(){
    invG=ksm(G,mod-2);
    int n;
    scanf("%lld",&n);
    init(n);
    for(int i=0;i<=n;++i)
        a[i]=(i&1?mod-inv[i]:inv[i]),
        b[i]=ksm(i,n)*inv[i]%mod;
    int limit=1;
    while(limit<=(n<<1)) limit<<=1;
    for(int i=0;i<=limit;++i)
        tr[i]=(tr[i>>1]>>1)|(i&1?limit>>1:0);
    NTT(a,limit,0);NTT(b,limit,0);
    for(int i=0;i<=limit;++i)
        a[i]=a[i]*b[i]%mod;
    NTT(a,limit,1);
    for(int i=0;i<=n;++i)
        printf("%lld ",a[i]);
    return 0;
}

顺便讲一下列的做法（

每个盒子的 EGF 显然就是 g(x)=\sum_{i=1}^n \frac{1}{i!}x^i=e^x-1，把盒子的 EGF 相乘就可以得到 (e^x-1)^k （其中 k 是盒子的个数）

然后就可以得到"第二类斯特林数"的 EGF 了。但是还有个问题就是盒子是相同的，而我们在推导 EGF 的过程中是把每个盒子按不同的来看待的，直接把这个"第二类斯特林数"除以 k! 即可，是非常显然的去重，然后就可以得到真正的第二类斯特林数。

至于 (e^x-1)^k 怎么算，直接多项式快速幂即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
const ll mod=167772161;
ll G=3,invG;
const int N=1200000;
ll ksm(ll b,int n){
    ll res=1;
    while(n){
        if(n&1) res=res*b%mod;
        b=b*b%mod; n>>=1;
    }
    return res;
}
int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)) x=(x*10+(ch-'0'))%mod,ch=getchar();
    return x;
}
int tr[N];
void NTT(ll *f,int n,int fl){
    for(int i=0;i<n;++i)
        if(i<tr[i]) swap(f[i],f[tr[i]]);
    for(int p=2;p<=n;p<<=1){
        int len=(p>>1);
        ll w=ksm((fl==0)?G:invG,(mod-1)/p);
        for(int st=0;st<n;st+=p){
            ll buf=1,tmp;
            for(int i=st;i<st+len;++i)
                tmp=buf*f[i+len]%mod,
                f[i+len]=(f[i]-tmp+mod)%mod,
                f[i]=(f[i]+tmp)%mod,
                buf=buf*w%mod;
        }
    }
    if(fl==1){
        ll invN=ksm(n,mod-2);
        for(int i=0;i<n;++i)
            f[i]=(f[i]*invN)%mod;
    }
}
void Mul(ll *f,ll *g,ll *p,int n,int m){
    m+=n;n=1;
    while(n<m) n<<=1;
    for(int i=0;i<n;++i)
        tr[i]=(tr[i>>1]>>1)|((i&1)?(n>>1):0);
    NTT(f,n,0);
    NTT(g,n,0);
    for(int i=0;i<n;++i) p[i]=f[i]*g[i]%mod;
    NTT(p,n,1);

}

void Inv(ll *f,ll *g,int m){
    if(m==1){
        g[0]=ksm(f[0],mod-2);
        return;
    }
    static ll w[N];
    Inv(f,g,(m+1)>>1);
    int n=1;
    while(n<(m<<1)) n<<=1;
    for(int i=0;i<m;++i) w[i]=f[i];
    for(int i=m;i<n;++i) w[i]=0;
    for(int i=0;i<n;++i)
        tr[i]=(tr[i>>1]>>1)|((i&1)?(n>>1):0);
    NTT(w,n,0);
    NTT(g,n,0);
    for(int i=0;i<n;++i)
        g[i]=((2*g[i]-g[i]*g[i]%mod*w[i]%mod)%mod+mod)%mod;
    NTT(g,n,1);
    for(int i=m;i<n;++i) g[i]=0; 
}
void diff(ll *f,ll *g,int n){
    for(int i=1;i<n;++i)
        g[i-1]=f[i]*i%mod;
    g[n-1]=0;
}
void integ(ll *f,ll *g,int n){
    for(int i=1;i<n;++i)
        g[i]=f[i-1]*ksm(i,mod-2)%mod;
    g[0]=0;
}
ll f_wf[N],f_inv[N],ans[N];
void Ln(ll *f,ll *g,int n){
    for(int i=0;i<(n<<2);++i) f_wf[i]=f_inv[i]=ans[i]=0;
    diff(f,f_wf,n);
    Inv(f,f_inv,n);
    Mul(f_wf,f_inv,ans,n,n);
    integ(ans,g,n);
}
void Exp(ll *f,ll *g,int m){
    if(m==1){
        g[0]=1;return;
    }
    Exp(f,g,(m+1)>>1);
    static ll w[N],ln[N];
    for(int i=0;i<m;++i) ln[i]=0;
    Ln(g,ln,m);
    int n=1;
    while(n<(m<<1)) n<<=1;
    for(int i=0;i<n;++i)
        tr[i]=(tr[i>>1]>>1)|(i&1?n>>1:0);
    for(int i=0;i<m;++i) w[i]=f[i];
    for(int i=m;i<n;++i) w[i]=0;
    NTT(w,n,0);NTT(g,n,0);NTT(ln,n,0);
    for(int i=0;i<n;++i)
        g[i]=g[i]*(1-ln[i]+w[i]+mod)%mod;
    NTT(g,n,1);
    for(int i=m;i<n;++i) g[i]=0;
}
int k2;
void Pow(ll *f,ll *g,int n,int k){
    static ll _f[N],lnf[N];
    ll deg=0;
    while(f[deg]==0) ++deg;
    if(deg*k>n) return;
    n-=deg;
    for(int i=0;i<n;++i)
        _f[i]=f[i+deg];
    ll f0=_f[0],inv0=ksm(_f[0],mod-2);
    for(int i=0;i<n;++i)
        _f[i]=_f[i]*inv0%mod;
    Ln(_f,lnf,n);
    for(int i=0;i<n;++i)
        lnf[i]=lnf[i]*k%mod;
    Exp(lnf,g,n);
    deg=deg*k2;
    for(int i=n+deg-1;i>=deg;--i)
        g[i]=g[i-deg]*ksm(f0,k2)%mod;
    for(int i=0;i<deg;++i) g[i]=0;
}
ll f[N],g[N];
ll inv[N],fac[N];
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=0;--i)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
string s;
signed main(){
    invG=ksm(G,mod-2);
    int n,k=0;
    cin>>n>>k;++n;
    if(k>=n){
        for(int i=0;i<n;++i) putchar('0'),putchar(' ');
        return 0;
    }
    k2=k;
    init(max(n,k));
    for(int i=1;i<n;++i)
        f[i]=inv[i];
    Pow(f,g,n,k);
    for(int i=0;i<n;++i)
        g[i]=g[i]*fac[i]%mod*inv[k]%mod,
        printf("%lld ",g[i]);
    return 0;
}

本来想再把 第一类斯特林数·行/列 给讲掉的，但这样博客实在太长了，就算了吧（

顺便一提第一类斯特林数·列的做法与第二类斯特林数·列的做法相似