发现网上没有我这种写法。。
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 ;
} /*
*/