Codeforces 932E Team Work 数学

发现网上没有我这种写法。。

i ^ k我们可以理解为对于每个子集我们k个for套在一起数有多少个。

那么我们问题就变成了任意可重复位置的k个物品属于多少个子集。

然后我们枚举k个物品所占位置的个数 i ，然后需要计算有多少种方案能把k个不同物品放入i个桶中。

这个东西可以用dp[ i ][ j ] 表示 i 个物品放入 j 个桶中的方案数。 dp[ i ][ j ] = dp[ i - 1 ][ j ] * j + dp[ i - 1 ][ j - 1 ] * j

然后就可以求答案啦。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int M = 2e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

LL n, k;

LL power(LL a, LL b) {

    LL ans = ;

    while(b) {

        if(b & ) ans = ans * a % mod;

        a = a * a % mod; b >>= ;

    }

    return ans;

}

LL comb(int n, int m) {

    if(n <  || n < m) return ;

    LL A = , B = ;

    for(int i = ; i < m; i++)

        A = A * (n - i) % mod, B = B * (i + ) % mod;

    return A * power(B, mod - ) % mod;

}

LL dp[N][N];

int main() {

    for(int i = ; i < N; i++) {

        for(int j = ; j <= i; j++) {

            if(j == ) dp[i][j] = ;

            else dp[i][j] = (dp[i-][j] * j % mod + dp[i-][j-] * j % mod) % mod;

        }

    }

    scanf("%lld%lld", &n, &k);

    LL ans = ;

    for(int i = ; i <= min(n, k); i++) {

        LL ret = comb(n, i);

        ret = ret * power(, n - i) % mod * dp[k][i] % mod;

        ans = (ans + ret) % mod;

    }

    printf("%lld\n", ans);

    return ;

}

/*

*/