CF932E Team Work

题面

题解

有一个非常玄学的公式：

$$ m^n=sum_{i=0}^nC_m^i imes S(n,i) imes i! $$

看一下$ ext{yyb}$的解释：

$m^n$理解为把$n$个不同的球放到$m$个不同的盒子中去。

那么我们枚举有几个盒子非空，用第二类斯特林数乘阶乘计算放置的方案数，最后求和就是结果。

所以原式等于：

$$ sum_{i=1}^nC_n^isum_{j=0}^iC_i^j imes S(k,j) imes j! \ =sum_{i=1}^nfrac{n!}{i!(n-i)!}sum_{j=0}^ifrac{S(k,j)}{(i-j)!} \ =sum_{j=0}^kS(k,j)sum_{i=j}^nfrac{n!}{(n-i)!}*frac{1}{(i-j)!} \ =sum_{j=0}^{k}S(k,j)sum_{i=0}^nfrac{n!}{(n-j)!}frac{(n-j)!}{(n-i)!(i-j)!} \ =sum_{j=0}^{k}S(k,j)frac{n!}{(n-j)!}sum_{i=0}^nC_{n-j}^{i-j} \ =sum_{j=0}^{k}S(k,j)frac{n!}{(n-j)!}2^{n-j} $$

暴力$ ext{O}(k^2)$预处理即可

代码

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x))

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while(ch != '-' && (!isdigit(ch))) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int Mod(1e9 + 7), Inv2(500000004), maxn(5010);
inline int fastpow(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1) ans = 1ll * ans * x % Mod;
		x = 1ll * x * x % Mod, y >>= 1;
	}
	return ans;
}

int n, k, S[maxn][maxn], ans;
int main()
{
#ifndef ONLINE_JUDGE
	file(cpp);
#endif
	n = read(), k = read(), S[0][0] = 1;
	for(RG int i = 1; i <= k; i++)
		for(RG int j = 1; j <= k; j++)
			S[i][j] = (S[i - 1][j - 1] + 1ll * S[i - 1][j] * j % Mod) % Mod;
	for(RG int j = 0, pow2 = fastpow(2, n), fac = 1; j <= std::min(n, k);
		pow2 = 1ll * pow2 * Inv2 % Mod, fac = 1ll * fac * (n - j) % Mod, ++j)
		ans = (ans + 1ll * S[k][j] * pow2 % Mod * fac % Mod) % Mod;
	printf("%d
", ans);
	return 0;
}