首页 > 其他分享 >CF932E

CF932E

时间:2022-10-24 22:11:27浏览次数:36  
标签:begin end int sum Bmatrix binom CF932E

先介绍这样一个等式:

\[n^m=\sum_{i=1}^{m}\begin{Bmatrix}m\\ i\end{Bmatrix}\times i!\times \binom{n}{i} \]

等式左边的组合意义是 \(m\) 个不同的球放入 \(n\) 个不同的盒子里的方案数。

右边就是枚举非空盒子的数量 \(i\),然后就是从 \(n\) 个里面选出 \(i\) 个盒子,乘上 \(i!\) 之后盒子就被认为是相同的了,然后再乘上把 \(m\) 个不同的球放入 \(i\) 个相同的盒子的方案数,即第二类斯特林数 \(\begin{Bmatrix}m\\ i\end{Bmatrix}\)。

然后这题要求的是

\[\sum_{i=1}^{n}\binom{n}{i}i^k \]

直接用上面的等式暴力展开:

\[=\sum_{i=1}^{n}\binom{n}{i}\sum_{j=1}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}i^{\underline j} \]

\[=\sum_{j=1}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}j!\sum_{i=1}^{n}\binom{n}{i}\binom{i}{j} \]

\[=\sum_{j=1}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}j!\sum_{i=1}^{n}\binom{n}{j}\binom{n-j}{i-j} \]

\[=\sum_{j=1}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}j!\binom{n}{j}\sum_{i=0}^{n-j}\binom{n-j}{i} \]

\[=\sum_{j=1}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}j!\binom{n}{j}2^{n-j} \]

然后 \(\mathcal O(k^2)\) 预处理第二类斯特林数什么的,就好了。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005, mod = 1e9 + 7;
int n, k;
int ans;
int S[N][N];

int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return res;
}

void init() {
	S[0][0] = 1;
	for (int i = 1; i <= k; ++i)
		for (int j = 1; j <= i; ++j)
			S[i][j] = (S[i - 1][j - 1] + 1ll * S[i - 1][j] * j % mod) % mod;
}

int main() {
	scanf("%d%d", &n, &k);
	init();
	for (int i = 1; i <= min(n, k); ++i) {
		int tmp = 1ll * S[k][i] * qpow(2, n - i) % mod;
		for (int j = n - i + 1; j <= n; ++j) tmp = 1ll * tmp * j % mod;
		ans = (ans + tmp) % mod;
	}
	printf("%d", ans);
	return 0;
}

标签:begin,end,int,sum,Bmatrix,binom,CF932E
From: https://www.cnblogs.com/Kobe303/p/16823201.html

相关文章