首页 > 其他分享 >CF1278F

CF1278F

时间:2022-10-25 07:33:04浏览次数:94  
标签:CF1278F int sum iq Bmatrix binom underline

CF932E 其实是差不多的捏

设 \(p=\dfrac{1}{m},q=1-p\),那么枚举第一张是王牌的次数,有如下式子:

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

后面那个 \(i^k\) 可以展开为第二类斯特林数:

\[=\sum_{i=1}^{n}\binom{n}{i}p^iq^{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}\sum_{i=1}^{n}\binom{n}{i}p^iq^{n-i}i^{\underline{j}} \]

考虑化简

\[\sum_{i=1}^{n}\binom{n}{i}p^iq^{n-i}i^{\underline{j}} \]

\[=\sum_{i=j}^{n}\binom{n}{i}p^iq^{n-i}\binom{i}{j}j! \]

\[=j!\binom{n}{j}\sum_{i=j}^{n}\binom{n-j}{i-j}p^iq^{n-i} \]

\[=n^{\underline{j}}\sum_{i=0}^{n-j}\binom{n-j}{i}p^{i+j}q^{n-j-i} \]

\[=n^{\underline{j}}p^j\sum_{i=0}^{n-j}\binom{n-j}{i}p^{i}q^{n-j-i} \]

注意到后面那个就是 \((p+q)^{n-j}\) 用二项式定理展开的形式,而 \(p+q=1\)。

所以

\[=n^{\underline{j}}p^j \]

那么答案就是

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

\(\mathcal O(k^2)\) 预处理斯特林数啥的就好了。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005, mod = 998244353;
int n, m, k, p;
int ans;
int S[N][N], mul[N], f[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;
	mul[0] = 1;
	for (int i = 1; i <= k; ++i) mul[i] = 1ll * mul[i - 1] * p % mod;
	f[0] = 1;
	for (int i = 1; i <= k; ++i) f[i] = 1ll * f[i - 1] * (n - i + 1) % mod;
}

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

标签:CF1278F,int,sum,iq,Bmatrix,binom,underline
From: https://www.cnblogs.com/Kobe303/p/16823695.html

相关文章