CF1278F Cards

首先考虑怎么计算x

如果只抽一次的话,期望次数应该是 $\frac 1 m$

然后考虑n次的期望应该就是 $\frac n m$

然后就不对了...因为没有的也有概率和权值为0啊....

\sum_{i}^n \binom n i i^k p^i (1-p)^{n-i}

可能这个p是 $\frac 1 m$

然后就能直接斯特林展开了

x^k=\sum_{i}^k S(k,i)\binom {x} {i} i!

首先枚举中了几次,然后抽取x次的概率就是

\sum_{x=0}^n \binom{x}{n}(\frac{1}{m})^x(\frac{m-1}{m})^{n-x}

权值?我们斯特林展开总不能展开期望吧?所以只能展开权值啊

\sum_{x=0}^n \binom{n}{x}(\frac{1}{m})^x(\frac{m-1}{m})^{n-x}\sum_{i=1}^kS[k][i]i!\binom{x}{i}

然后这个式子我们神乎其技的展开组合数

\sum_{x=0}^n (\frac{1}{m})^x(\frac{m-1}{m})^{n-x}\sum_{i=1}^kS[k][i]i!\binom{x}{i}\binom{n}{x}

\sum_{x=0}^n (\frac{1}{m})^x(\frac{m-1}{m})^{n-x}\sum_{i=1}^kS[k][i]i!\binom{n}{i}\binom{n-i}{x-i}

有i!!,所以我们展开其中的第一个组合数吸收

\sum_{x=0}^n (\frac{1}{m})^x(\frac{m-1}{m})^{n-x}\sum_{i=1}^kS[k][i]\frac{n!}{(n-i)!}\binom{n-i}{x-i}

然后不太会啊?因为最后面的组合数....想办法二项式反演?

\sum_{i=1}^kS[k][i]\frac{n!}{(n-i)!}\sum_{x=0}^n (\frac{1}{m})^x(\frac{m-1}{m})^{n-x}\binom{n-i}{x-i}

因为x-i是负数的时候没用
这个式子要一点神乎其技的操作来把形式搞出来了,枚举x'=x-i

\sum_{i=1}^kS[k][i]\frac{n!}{(n-i)!}\sum_{x'=0}^{n-i} (\frac{1}{m})^{x'+i}(\frac{m-1}{m})^{n-x'-i}\binom{n-i}{x'}

然后就没有了啊,右边搞出二项式反演了!n-i'和x!

\sum_{i=1}^kS[k][i]\frac{n!}{(n-i)!} (\frac{1}{m})^i

直接做即可

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXK = 5007;
ll ans, n, k, m;
int S[MAXK][MAXK], fac[MAXK], ifac[MAXK], f[MAXK];

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline void init() {
	fac[0] = fac[1] = 1;
	ifac[0] = ifac[1] = 1;
	S[0][0] = 1;
	for(int i = 1; i <= k; ++i) {
		for(int j = 1; j <= k; ++j) {
			S[i][j] = (1ll * S[i - 1][j] * j % P + S[i - 1][j - 1]) % P;
		}
	}
	for(int i = 1; i <= k; ++i) {
		fac[i] = 1ll * i * fac[i - 1] % P;
	}
	ifac[k] = ksm(fac[k], P - 2);
	for(int i = k - 1; i > 1; --i) {
		ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	}
	f[0] = 1;
	//n!/(n-1)!
	for(int i = 1; i <= k; ++i) {
		f[i] = 1ll * f[i - 1] * (n - i + 1) % P;
	}
	return ;
}

inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

int main() {
	scanf("%lld%lld%lld", &n, &m, &k);
	init();
	ll wn = ksm(m, P - 2), w = 1;
	for(int i = 1; i <= k; ++i) {
		w = w * wn % P;
		add(ans, w * S[k][i] % P * f[i] % P);
	}
	printf("%lld\n", ans);
	return 0;
}

夏晓光(loveJY)的博客

SDSCDay1