斯特林数与贝尔数求法

现在在码两篇博客，一篇lin4xu杂题全题解，一篇博弈论。然后我现在一个都没码完又开一个斯特林数。

我们先不管斯特林数有什么性质，这个以后专门开个数数专题。直接开始看怎么求一行/一列。

上下划线比较频繁，但是cnblogs显示不了。请主观猜测或者右键公式开SVG或者看LaTeX源码。

第二类斯特林数·行

我们有

二项式反演一下

嗯卷。

void getstiring(int n,int a[]){
    for(int i=0;i<=n;i++){
        a[i]=(i&1)?mod-inv[i]:inv[i];
        b[i]=1ll*qpow(i,n)*inv[i]%mod;
    }
    n++;get(n<<1);
    ntt(a,wl,1);ntt(b,wl,1);
    for(int i=0;i<wl;i++)a[i]=1ll*a[i]*b[i]%mod;
    ntt(a,wl,-1);
}

第一类斯特林数·行

显然

考虑怎么求这个东西。同样显然

直接套多项式平移即可。注意倍增的时候要分奇偶讨论一下，有时候要算 \(x^{\overline n}(x+n)\) ，暴力扫两遍乘就行了。

void getstiring(int n,int b[]){
    if(n==1){
        b[1]=1;return;
    }
    getstiring(n>>1,b);
    move(b,(n>>1)+1,n>>1,a);
    ntt(b,wl,1);ntt(a,wl,1);
    for(int i=0;i<wl;i++)b[i]=1ll*b[i]*a[i]%mod;
    ntt(b,wl,-1);
    for(int i=n+1;i<wl;i++)b[i]=0;
    if(n&1){
        for(int i=n;i>=1;i--)b[i]=(b[i-1]+1ll*(n-1)*b[i]%mod)%mod;
        b[0]=1ll*b[0]*(n-1)%mod;
    }
}

第二类斯特林数·列

command_blocks 给出了一个优秀的 \(O(n\log n)\) 小常数解法。

当然你可以写个多项式快速幂直接套一列第二类斯特林数的生成函数

但是我们有不用 \(\exp\) 的方法。

套路设 \(F_l(x)=\sum_{i=0}\begin{Bmatrix}i\\k\end{Bmatrix}x^i\) ，然后开始化：

解方程得到

边界 \(F_0(x)=1\) ，所以

现在我们求 \(\prod_{i=1}^k1-ix\) 。提取公因式 \(x^k\) ，有

发现 \(\prod_{i=1}^k(x-i)\) 翻转之后就是 \(\prod_{i=1}^k(x^{-1}-i)\) 。然后 \(\prod_{i=1}^k(x-i)\) 显然是 \(\frac{x^{\underline k+1}}{x}\) 。这个也可以直接倍增多项式平移搞定。

void solve(int n,int b[]){
    if(n==1){
        b[1]=1;return;
    }
    solve(n>>1,b);
    move(b,(n>>1)+1,mod-(n>>1),a);
    ntt(b,wl,1);ntt(a,wl,1);
    for(int i=0;i<wl;i++)b[i]=1ll*b[i]*a[i]%mod;
    ntt(b,wl,-1);
    for(int i=n+1;i<wl;i++)b[i]=a[i]=0;
    if(n&1){
        for(int i=n;i>=1;i--)b[i]=(b[i-1]+1ll*(mod-n+1)*b[i]%mod)%mod;
        b[0]=1ll*b[0]*(mod-n+1)%mod;
    }
}
void getstiring(int n,int k,int a[]){
    if(n<k)return;
	solve(k+1,b);
    reverse(b,b+k+2);
    for(int i=0;i<=n;i++)a[i]=0;
    getinv(n-k+1,b,a);
    for(int i=n;i>=k;i--)a[i]=a[i-k];
    for(int i=0;i<k;i++)a[i]=0;
}

第一类斯特林数·列

第一类斯特林数的 \(\rm EGF\) ：

其实里面那个 \(\ln\) 不用多项式 \(\ln\) ，直接按定义把每个系数放上去就行了。

void getstiring(int n,int a[],int k){
    if(n<=k)return;
    for(int i=0;i<n-k;i++)a[i]=qpow(i+1,mod-2);
    getpow(n-k,a,b,k);
    for(int i=n-k-1;i>=0;i--)a[i+k]=b[i];
    for(int i=0;i<k;i++)a[i]=0;
    int inv=qpow(jc[k],mod-2);
    for(int i=0;i<n;i++)a[i]=1ll*a[i]*jc[i]%mod*inv%mod;
}

贝尔数

一行斯特林数的和。组合意义推 \(\rm EGF\) 可以得到生成函数

套。

void getbell(int n,int a[]){
    for(int i=n-1;i>=1;i--)a[i]=inv[i]=1ll*inv[i+1]*(i+1)%mod;
    getexp(n,a,b);
    for(int i=0;i<n;i++)a[i]=1ll*b[i]*jc[i]%mod;
}

原文地址：http://www.cnblogs.com/gtm1514/p/16797095.html