2021多校10 Game of Death 容斥原理,FFT

题意:

有$n$个哈皮要打枪,每个人会独立随机选择一个其他人瞄准,然后所有人同时开枪。

每个人只开一枪,并且有$p$的概率打中(每个人是否打中是独立的)。

问最后剩$0$~$n$个人存活的概率,对$998244353$取模。


如果没有“不能瞄准自己”的限制的话就很简单了,但是这里有这个限制。

我们可以考虑容斥原理,选择一个集合$S$,限制$S$中的人都没有死,但是其他人不管死活。假设这个概率是$g(S)$,显然所有集合大小相等的$S$的答案都是相同的,不妨设$|S| = i$时答案是$g_i$,可以得到

$$ g_i = \left(\frac {i – 1} {n – 1} (1 – p) + \frac {n – i} {n – 1}\right) ^ i \left(\frac i {n – 1} (1 – p) + \frac {n – i – 1} {n – 1}\right) ^ {n – i} $$

出奇的简单,只需要分是否在$S$中讨论就行了。因为其他人死活不考虑,所以只需要使$S$中所有人没被打到。

考虑题目要求的东西,设$f(S)$表示恰好只有$S$中的人没有死,其他人都死了,那么就有

$$ g(S) = \sum_{T \supset S} f(T) $$

根据容斥原理,从$g$推$f$的式子就是

$$ f(S) = \sum_{T \supset S} (-1) ^ {|T| – |S|} g(T) $$

$f$也可以写成$f_i$的形式:

$$ f_i = \sum_{k = i} ^ n (-1) ^ {k – i} {{n – i} \choose {k – i}} a_k $$

可以化成一个卷积形式。

注意$f_i$仅仅针对单个集合$S$,然而实际上每个$S$都有可能成为最后活着的人,所以输出时要乘上选择$S$的组合数。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = (1 << 20) + 5, p = 998244353;

int qpow(int a, int b) {
	int ans = 1;

	while (b) {
		if (b & 1)
			ans = (long long)ans * a % p;
		
		b >>= 1;
		a = (long long)a * a % p;
	}
	
	return ans;
}

int ntt_n, omega[maxn], omega_inv[maxn];

void NTT_init(int n) {
	ntt_n = n;

	int wn = qpow(3, (p - 1) / n);

	omega[0] = omega_inv[0] = 1;

	for (int i = 1; i < n; i++)
		omega_inv[n - i] = omega[i] = (long long)omega[i - 1] * wn % p;
}

void NTT(int *a, int n, int tp) {
	for (int i = 1, j = 0, k; i < n - 1; i++) {
		k = n;
		do
			j ^= (k >>= 1);
		while (j < k);

		if (i < j)
			swap(a[i], a[j]);
	}

	for (int k = 2, m = ntt_n / 2; k <= n; k *= 2, m /= 2)
		for (int i = 0; i < n; i += k)
			for (int j = 0; j < k / 2; j++) {
				int w = (tp > 0 ? omega : omega_inv)[m * j];

				int u = a[i + j], v = (long long)w * a[i + j + k / 2] % p;

				a[i + j] = u + v;
				if (a[i + j] >= p)
					a[i + j] -= p;
				
				a[i + j + k / 2] = u - v;
				if (a[i + j + k / 2] < 0)
					a[i + j + k / 2] += p;
			}
	
	if (tp < 0) {
		int inv = qpow(n, p - 2);
		for (int i = 0; i < n; i++)
			a[i] = (long long)a[i] * inv % p;
	}
}

int fac[maxn], fac_inv[maxn], inv[maxn];
int a[maxn], f[maxn], g[maxn];

int main() {

	ios::sync_with_stdio(false);

	int n, u, v;
	cin >> n >> u >> v;

	int Q = (1 - (long long)u * qpow(v, p - 2)) % p;
	if (Q < 0)
		Q += p;
	
	fac[0] = fac_inv[0] = 1;
	for (int i = 1; i <= n; i++) {
		fac[i] = (long long)fac[i - 1] * i % p;
		inv[i] = qpow(i, p - 2);
		fac_inv[i] = (long long)fac_inv[i - 1] * inv[i] % p;
	}

	int di = qpow(inv[n - 1], n);
	for (int i = 0; i <= n; i++) {
		int tp = qpow(((long long)(i - 1) * Q + (n - i)) % p, i),
			tq = qpow(((long long)i * Q + (n - i - 1)) % p, n - i);
		
		a[i] = (long long)tp * tq % p * di % p;
	}

	for (int i = 0; i <= n; i++) {
		f[i] = (long long)a[n - i] * fac_inv[i] % p;
		g[i] = fac_inv[i];
		if (i & 1)
			g[i] = p - g[i];
	}

	int N = 1;
	while (N <= n * 2)
		N *= 2;
	
	NTT_init(N);

	NTT(f, N, 1);
	NTT(g, N, 1);

	for (int i = 0; i < N; i++)
		f[i] = (long long)f[i] * g[i] % p;
	
	NTT(f, N, -1);

	for (int i = 0; i <= n; i++)
		cout << (long long)fac[n] * fac_inv[i] % p * f[n - i] % p << "\n";
	
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注