LOJ#2541. 「PKUWC2018」猎人杀

题目地址：["噔"](https://loj.ac/problem/2541)

题目给定的条件不太好求。
发现原题死了人之后概率的分母会变，十分不可做。

然后就有一步神转化了，我们将原题改为打死人之后这个人并不出局，而是被打上标记。如果开枪射中打标记的人，那么这一枪无效，重新射击。

这样我们发现，分母一定了，容易了许多。

整理一下，发现我们没有办法确切算出$1$在最后一个死的概率，但是我们可以确切算出至少有$k$个人死在$1$后面垫底的概率。
这样我们就可以使用容斥原理，设$f(i)$是选$i$个人死在后面垫底的概率：
$$f(0) = \sum^n_{i=1}(-1)^{i+1}f(i)$$
考虑怎么先选$i$个人死后面垫底。

我们选$k$个人出来，并且让$1$死之前开的枪都没开中这$k$个人即可。
设$k$个人组成的集合为$V$，全集为$U$。
且定义：
$$S_A = \sum_{i\in A} w_i$$
那么对于集合$V$，概率为：
$$\sum^{\infty}_{i=0}(1-\frac{w_1+S_V}{S_U})^i\frac{w_1}{S_U}$$
利用简单的生成函数知识，上面这个泰勒展开回去化简变成：
$$\frac{w_1}{S_V+w_1}$$
发现本题有一个重要信息：$\sum w_i\le 10^5$。
考虑把$S_V$相同的集合$V$一起处理。
这样因为$S_V$是相同的，我们只需要知道每一种$\frac{w_1}{S_V+w_1}$前面的系数是多少就行了。
考虑每一个人可以取或者不取，把容斥系数也算进去，那么每多取一个人就要添一个负号，相当于计算这个多项式：
$$\prod_{i=2}^n(1-x^{w_i})$$
它第$i$项的系数就是$S_V=i$时的系数。
我们已经可以利用分治$NTT$解决这道题，复杂度$O(n log^2 n)$。

但是如果这样做，那就比较$low$了

一个多项式爱好者怎么能止步于此呢？

这个东西我们可以$O(nlogn)$求！

我们发现这样一个事实：
$$ln(1-x^a)=-\sum^{\infty}_{i=0}\frac{x^{ai}}{i}$$
很惊喜的发现！因为这样我们就可以毫不费力的求出
$$\sum^{n}_{i=2} ln(1-x^{w_i})$$
具体来说对$w_i$做一个桶，然后一次枚举倍数处理出这个多项式，这一部分复杂度为$O(n\ ln(n))$。
更惊喜的是，答案已经呼之欲出了，因为：
$$ln(\prod_{i=2}^n(1-x^{w_i}))=\sum^{n}_{i=2} ln(1-x^{w_i})$$
这里已经太明显了！对这个多项式$exp$即可。

总复杂度$O(nlooooooooooogn+nlogn)$

事实证明$exp$跑不过$log^2$……

```
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#define LL long long
using namespace std;
const int mod = 998244353, sqrt2 = 116195171,
isqrt2 = 557219762, IG = 332748118, G = 3;
const int maxn = 4e5 + 5;

LL step[maxn], sinv[maxn];
LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}
void pre(int n) {
	step[0] = sinv[0] = 1;
	for(register int i = 1; i <= n; ++i)
		step[i] = step[i - 1] * i % mod;
	sinv[n] = fpow(step[n], mod - 2);
	for(register int i = n - 1; i >= 1; --i)
		sinv[i] = sinv[i + 1] * (i + 1) % mod;
}
void Add(int &x, const int &b) {
	x += b; if(x >= mod) x -= mod;
}
void Dec(int &x, const int &b) {
	x -= b; if(x < 0) x += mod;
}
namespace Poly {
	struct PLG {
		vector<int > x;
		PLG(){} PLG(int n) {x.resize(n + 1);}
		int deg() const {return x.size() - 1;}
		void read(int n) {
			int u;
			for(register int i = 0; i <= n; ++i)
				scanf("%d", &u), x.push_back(u);
		}
		void prt() {
			for(register int i = 0; i < x.size(); ++i)
				printf("%d ", x[i]);
			putchar('\n');
		}
	};
	int mx2p, N, RL[maxn];
	LL w[maxn];
	void init(int n) {
		for(N = 1, mx2p = 0; N <= n; N <<= 1, ++mx2p);
		for(register int i = 1; i < N; ++i)
			RL[i] = (RL[i >> 1] >> 1) | ((i & 1) << mx2p - 1);
	}
	void NTT(PLG &A, int t) {
		for(register int i = 0; i < N; ++i)
			if(i < RL[i]) swap(A.x[i], A.x[RL[i]]);
		LL Wn, x, y; w[0] = 1;
		for(register int i = 1; i < N; i <<= 1) {
			if(t > 0) Wn = fpow(G, (mod - 1) / (i << 1));
			else Wn = fpow(IG, (mod - 1) / (i << 1));
			for(register int j = 1; j < i; ++j)
				w[j] = w[j - 1] * Wn % mod;
			for(register int p = i << 1, j = 0; j < N; j += p) {
				for(register int k = 0; k < i; ++k) {
					x = A.x[j + k], y = w[k] * A.x[j + i + k] % mod;
					A.x[j + k] = (x + y) % mod;
					A.x[j + i + k] = (x - y + mod) % mod;
				}
			}
		}
		if(t < 0) {
			LL invn = fpow(N, mod - 2);
			for(register int i = A.x.size() - 1; i >= 0; --i)
				A.x[i] = A.x[i] * invn % mod;
		}
	}
	void operator %=(PLG &A, const int &b) {A.x.resize(b);}
	PLG operator +(const PLG &A, const PLG &B) {
		PLG C(max(A.deg(), B.deg()));
		for(register int i = A.deg(); i >= 0; --i)
			Add(C.x[i], A.x[i]);
		for(register int i = B.deg(); i >= 0; --i)
			Add(C.x[i], B.x[i]);
		return C;
	}
	PLG operator -(const PLG &A, const PLG &B) {
		PLG C(max(A.deg(), B.deg()));
		for(register int i = A.deg(); i >= 0; --i)
			Add(C.x[i], A.x[i]);
		for(register int i = B.deg(); i >= 0; --i)
			Dec(C.x[i], B.x[i]);
		return C;
	}
	PLG operator *(const PLG &A, const PLG &B) {
		PLG pa = A, pb = B;
		int len = A.deg() + B.deg();
		init(len);
		pa.x.resize(N), pb.x.resize(N);
		NTT(pa, 1), NTT(pb, 1);
		for(register int i = 0; i < N; ++i)
			pa.x[i] = 1ll * pa.x[i] * pb.x[i] % mod;
		NTT(pa, -1), pa %= (len + 1);
		return pa;
	}
	PLG operator % (const PLG &A, const int &k) {
		PLG C = A; return C %= k, C;
	}
	PLG operator * (const int &k, const PLG &A) {
		PLG C = A;
		for(register int i = 0; i <= C.deg(); ++i)
			C.x[i] = 1ll * C.x[i] * k % mod;
		return C;
	}
	PLG inv(const PLG &A, const int &k) {
		PLG F; F.x.push_back(fpow(A.x[0], mod - 2));
		for(register int l = 2; (l >> 1) < k; l <<= 1)
			F = 2 * F - ((A % l) * (F * F) % l);
		return F % k;
	}
	PLG dg(const PLG &A) {
		PLG C(A.deg() - 1);
		for(register int i = A.deg(); i >= 1; --i)
			C.x[i - 1] = 1ll * A.x[i] * (i) % mod;
		return C;
	}
	PLG ig(const PLG &A) {
		int d = A.deg();
		PLG C(d + 1);
		for(register int i = d; i >= 0; --i) {
			C.x[i + 1] = 1ll * A.x[i] * fpow(i + 1, mod - 2) % mod;
		}
		return C;
	}
	PLG ln(const PLG &A, const int &k) {
		return ig(inv(A, k) * dg(A) % (k));
	}
	PLG exp(const PLG &A, const int &k) {
		PLG F; F.x.push_back(1);
		for(register int l = 2; (l >> 1) < k; l <<= 1)
			F = (F * (A % l - ln(F, l)) % l) + F;
		return F % k;
	}
}
using namespace Poly;
int n, v[maxn], ton[maxn], sum, ans;
PLG A;
int main() { 
	scanf("%d", &n);
	scanf("%d", &v[1]); 
	for(register int i = 2; i <= n; ++i)
		scanf("%d", &v[i]), sum += v[i], ++ton[v[i]];
	A.x.resize(sum + 1);
	for(register int k = 1; k <= sum; ++k)
		for(register int i = k; i <= sum; i += k)
			Dec(A.x[i], ton[k] * fpow(i / k, mod - 2) % mod);
	//A.prt();
	A = exp(A, sum + 1);
	//A.prt();
	for(register int i = 0; i <= sum; ++i) {
		ans += A.x[i] * 
				(1ll * v[1] * fpow(v[1] + i, mod - 2) % mod) % mod;
		ans %= mod;
	}
	printf("%d", ans);
	return 0;
} 
```

Rockdu's Blog

导航

最近发表

大佬们的友链