CF 932E Team Work

发布时间：2020-12-14 05:17:20 所属栏目：大数据来源：网络整理

导读：推式子题。首先有公式： $$n^k = n^k = sum_{i = 0}^{k}binom{n}{i}S(k,i)*i!$$ 其中$S$表示第二类斯特林数。左边表示$k$个不同的小球放$n$个不同的盒子允许有空盒的方案数，而右边先枚举非空盒的数量，选择非空的盒子，然后再把$k$个小球全部放入，因为

推式子题。

首先有公式：

$$n^k = n^k = sum_{i = 0}^{k}binom{n}{i}S(k,i)*i!$$

其中$S$表示第二类斯特林数。

左边表示$k$个不同的小球放$n$个不同的盒子允许有空盒的方案数，而右边先枚举非空盒的数量，选择非空的盒子，然后再把$k$个小球全部放入，因为盒子是不同的，所以还要乘上$i!$。

把公式代进去：

$$sum_{i = 1}^{n}binom{n}{i}i^k$$

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

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

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

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

注意到

$$sum_{i = 0}^{n - 1}binom{n - j}{i} = 2^{n - j} - [j == 0]$$

那么就可以直接算了。

第二类斯特林数有递推公式$S(n,m) = S(n - 1,m - 1) + m * S(n - 1,m)$。

时间复杂度$O(k^2)$。

Code：

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 5005;
const ll P = 1e9 + 7;

ll f[N],s2[N][N],bin[N];

inline ll fpow(ll x,ll y) {
    ll res = 1;
    for (; y > 0; y >>= 1) {
        if (y & 1) res = res * x % P;
        x = x * x % P;
    }
    return res;
}

int main() {
    int n,k;
    scanf("%d%d",&n,&k);
    
    s2[0][0] = 1;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= i; j++)
            s2[i][j] = (s2[i - 1][j - 1] + 1LL * j * s2[i - 1][j]) % P;
    
    f[0] = 1,bin[0] = fpow(2,n);
    ll inv2 = fpow(2,P - 2);
    for (int i = 1; i <= k; i++) {
        f[i] = f[i - 1] * (n - i + 1) % P;
        bin[i] = bin[i - 1] * inv2 % P;    
    }
    
    ll ans = 0;
    for (int i = 0; i <= k; i++)
        ans = (ans + s2[k][i] * f[i] % P * (bin[i] - (i == 0)) % P) % P;
    
    printf("%lldn",ans);
    return 0;
}

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!