第二类斯特林数总结

· · 个人记录

下降幂&上升幂

下降幂x^n=x(x-1)...(x-n+1)

上升幂x^n=x(x+1)...(x+n-1)

并且满足,(-x)的下降幂等于(-1)x的上升幂

第二类斯特林数:

S(n,k)=S(n-1,k-1)+S(n-1,k)*k

通项公式:

S(n,k)=\frac{1}{k!} \sum_{i=0}^k(-1)^kC_{k}^i(k-i)^n

容斥k个盒子i个盒子不选,每个人都对应(k-i)种选择

没有标号所以再比一个k即可

例题:

HEOI/TJOI 求和

解:

我们可以把第二类斯特林数拆开:

于是可以得到:

\sum_{i=0}^n\sum_{j=0}^nS(i,j)2^jj! =\sum_{i=0}^n\sum_{j=0}^n2^j\sum_{k=0}(-1)^kC_{j}^k(j-k)^i =\sum_{j=0}^n2^jj!\sum_{k=0}\frac{(-1)^k}{k!}\frac{\sum_{i=0}^n(j-k)^i}{j-k!}

上面的那一个\sum_{i=0}^n(j-k)^i是等比数列求和

我们发现后面刚好是一个卷积的形式

NTT搞一下就行了

最后再乘一个2^jj!

代码:


#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 998244353;
const int N = 8e5 + 101;
int n, jc[N], ans, r[N];
int a[N], b[N], res[N];

int ksm(int a,int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod; b >>= 1;
    }
    return res;
}

int get_val(int q,int n)
{
    if(q == 1) return n + 1;
    return (mod + 1 - ksm(q,n + 1)) * ksm(mod + 1 - q,mod - 2) % mod;
}

void NTT(int *A,int len,int flag)
{
    for(int i = 0;i < len; i++)
       if(i < r[i]) swap(A[i],A[r[i]]);
    for(int l = 1;l < len; l <<= 1)
    {
        int w1 = ksm(3,flag ? (mod - 1) / (l << 1) : (mod - 1) - (mod - 1) / (l << 1));
        for(int j = 0;j < len;j += l << 1)
        {
            int w = 1;
            for(int k = 0;k < l;k ++,w = (w * w1) % mod)
            {
                int t = (A[j + k + l] * w) % mod;
                A[j + k + l] = (A[j + k] - t + mod) % mod;
                A[j + k] = (A[j + k] + t) % mod;
            }
        }
    }
    int inv = ksm(len,mod - 2);
    if(!flag)
        for(int i = 0;i < len; i++)
           A[i] = (A[i] * inv) % mod;
}

signed main()
{
    cin >> n;
    jc[0] = 1;
    for(int i = 1;i <= n; i++) 
        jc[i] = (jc[i - 1] * i) % mod;
    int len = 1;
    while(len <= n + n + 2) len <<= 1;
    for(int i = 0;i < len; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) * (len >> 1));
    for(int i = 0;i <= n; i++)
        a[i] = (i % 2 == 0 ? 1 : -1) * ksm(jc[i],mod - 2) % mod;
    for(int i = 0;i <= n; i++)
        b[i] = (get_val(i,n) * ksm(jc[i],mod - 2)) % mod;
    NTT(a,len,1);
    NTT(b,len,1);
    for(int i = 0;i < len; i++)
        res[i] = (a[i] * b[i]) % mod;
    NTT(res,len,0);
    int ans = 0;
    for(int i = 0;i <= n; i++)
    {
        ans = (ans + ksm(2,i) * jc[i] % mod * res[i] % mod) % mod;
    }
    cout << ans << endl;
}