cf932E. Team Work(第二类斯特灵数组合数)

attack

发布于 2018-09-30 10:01:01

3450

发布于 2018-09-30 10:01:01

文章被收录于专栏：数据结构与算法数据结构与算法

题意

题目链接

Sol

这篇题解写的非常详细

首先要知道第二类斯特灵数的一个性质

$$m^n = \sum_{i = 0}^m C_{n}^i S(n, i) i!$$

证明可以考虑组合意义：$m^n$是把$n$个不同的球放到$m$个不同的盒子里的方案数

然后用这个式子展开$i^k$，把组合数展开，会得到这样一个式子

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

发现不是很好搞，但是考虑到当$j > k$时$S(k, j) = 0$，于是可以先枚举$S(k, j)$的贡献

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

把后面构造成组合数的形式

最终会得到

$$\sum_{j=0}^{k}S(k,j)\frac{n!}{(n-j)!}2^{n-j}$$

注意这里的阶乘是不能直接推的，可以维护化简之后的结果。

然后就做完了。

经验：

看到$i^k$想一想第二类斯特灵数

循环复杂度过高时考虑更换枚举顺序

看到分子分母中有阶乘时尝试构造组合数

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5001, mod = 1e9 + 7, inv2 = 500000004;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, K, s[MAXN][MAXN];
int fastpow(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = 1ll * base * a % mod;
        a = 1ll * a * a % mod; p >>= 1;
    }
    return base;
}
int main() {
    s[0][0] = 1;
    cin >> N >> K;
    for(int i = 1; i <= K; i++)
        for(int j = 1; j <= K; j++)
            s[i][j] = (s[i - 1][j - 1] + 1ll * s[i - 1][j] * j % mod) % mod;
    int ans = 0, nv = 1, po2 = fastpow(2, N);
    for(int i = 0; i <= min(K, N); po2 = 1ll * po2 * inv2 % mod, nv = 1ll * nv * (N - i) % mod, i++)
        (ans += (1ll * s[K][i] * nv % mod * po2 % mod)) %= mod;
    cout << ans % mod;
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-09-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度