BZOJ4555 求和

题意

设第二类斯特林数为 $S(n,k)$ 表示将 $n$ 个元素分为 $k$ 个无差异集合的方案数

$$ f(n)=\sum_{i=0}^{n}\sum_{j=0}^{i}S(i,j)\times 2^j \times (j!) $$

题解

发现当 $j>i$ 时后面的贡献为 $0$ 所以后面 $j$ 的范围可以枚举到 $n$ ,即
$$ f(n)=\sum_{i=0}^{n}\sum_{j=0}^{n}S(i,j)\times 2^j \times (j!) $$
首先推一下第二类斯特林数
$$ S(n,k)=\frac{1}{k!}\sum_{i=0}^{k}(-1)^i C_k^i (k-i)^n $$

然后将其带入原式
$$f(n)=\sum_{i=0}^{n}\sum_{j=0}^{n}\sum_{k=0}^{j}(-1)^k C_j^k(j-k)^i\frac{1}{j!} \times 2^j\times j!$$
$$ f(n)=\sum_{i=0}^{n}\sum_{j=0}^{n}\sum_{k=0}^{j}(-1)^k\frac{j!}{k!(j-k)!}(j-k)^i\times 2^j $$
约分,将 $i$ 的求和放到后面
$$f(n)=\sum_{j=0}^{n}j!\times 2^j\sum_{k=0}^{j}\frac{(-1)^k}{k!}\times\cfrac{\sum_{i=0}^{n}(j-k)^i}{(j-k)!} $$

$$ a(i)=\frac{(-1)^i}{i!}, b(i)=\frac{\sum_{k=0}^{n}i^k}{i!} $$
然后后面那块东西就变成了 $a,b$ 的卷积了呗
$$ f(n)=\sum_{j=0}^{n}j!\times 2^j \times a\cdot b$$
由于模 $998244353$ 这个好模数,所以直接把 $a,b$ 写出来做一遍 $NTT$ 然后和一下就行了

代码

#define MAX_N 2000007
#define MOD 998244353
#define G 3LL

int N;
ll a[MAX_N], b[MAX_N], c[MAX_N];
int r[MAX_N];

inline void input () {
    read(N);
}

inline void init () {
    ll up = 1, dn = 1;
    for (int i = 0; i <= N; ++i) {
        a[i] = up * quick_pow(dn, MOD - 2) % MOD;
        up *= -1LL;
        (dn *= (ll)(i + 1)) %= MOD;
    }
    up = 1, dn = 1;
    for (int i = 0; i <= N; ++i) {
        b[i] = up * quick_pow(dn, MOD - 2) % MOD;
        if (i == 0)
            up = N + 1;
        else
            up = (quick_pow((ll)(i + 1), (ll)(N + 1)) - 1 + MOD) % MOD * quick_pow((ll)i, MOD - 2) % MOD;
        (dn *= (ll)(i + 1)) %= MOD;
    }
}

inline void solve () {
    int M = 1, len = 0;
    while (M <= (N << 1) + 1) M <<= 1, ++len;
    for (int i = 0; i < M; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1);
    NTT(a, M, 1), NTT(b, M, 1);
    for (int i = 0; i < M; ++i)
        a[i] = a[i] * b[i] % MOD;
    NTT(a, M, -1);
    ll res = 0, bs = 1;
    for (int i = 0; i <= N; ++i) {
        (res += a[i] * bs % MOD) %= MOD;
        (bs *= (ll)(i + 1) * 2LL % MOD) %= MOD;
    }
    printf("%lld\n", res);
}

int main () {
    input();
    init();
    solve();
    return 0;
}

引用资料

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注