[PKUWC2018] 猎人杀

一、题目

听说过这题很久了，这么经典怎么能不做呢？

点此看题

二、解法

由于概率一直在变算着麻烦得很，有一个神奇 \(\tt idea\) 就是我们乱开枪，如果这一枪在鞭尸那么就再开一枪，知道打死第一个人为止。这种策略的证明也不难，对于一个人被打到的概率都只和 \(w_i\) 的比值有关。

然后还是不会做，一个想都不敢想的方法是指数级容斥，枚举集合 \(S\) 表示至少集合 \(S\) 中的人在 \(1\) 的后面死掉，那么答案是：

这一步妙极了，我们要主动使用容斥而不是看着像容斥才用（和 \(\tt cdq\) 差不多）而不是看着很像再用容斥，有很多方法能把容斥的复杂度降下来，常见的就是 \(dp\) 维护容斥系数。

\[\sum_{S}(-1)^{|S|}P(S) \]

其中 \(P(S)\) 表示至少集合 \(S\) 中的人在 \(1\) 后面死的概率，那么可以打无限枪，只要不打到 \(1\) 和 \(S\) 中的人就可以，然后我们再给 \(1\) 补一枪，这样可以写出 \(P(S)\) 的表达式了：

\[P(S)=\sum_{i=0}^\infty(\frac{tot-a[1]-sum[S]}{tot})^i\times\frac{a[1]}{tot} \]

直接把他当母函数写闭形式：

\[P(S)=\frac{1}{1-\frac{tot-a[1]-sum[S]}{tot}}\times\frac{a[1]}{tot}=\frac{a[1]}{a[1]+sum[S]} \]

发现就只有 \(sum[S]\) 需要算一算了，发现这就是一个背包问题，很容易 \(O(n^2)\) 解决啊。

再回去看一眼题目，\(\sum a_i\leq 10^5\)，也就是总容量是很小的，那么不难想到用生成函数优化背包。有 \(n-1\) 个形如 \(1-x^{a}\) 这样的函数我们要求他的卷积，那么直接分治就可以了。

注意分治的时候要按容量对半分，网上的题解大多是从中间分一半，我觉得这样是错的，但是我不是特别清楚怎么卡额。一定要这样才能说明复杂度是 \(O(n\log^2 n)\)

#include 
#include 
using namespace std;
const int M = 200005;
const int MOD = 998244353;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,ans,w[M],s[M],f[M];
namespace poly
{
	int len,A[M],B[M],rev[M];
	int qkpow(int a,int b)
	{
		int r=1;
		while(b>0)
		{
			if(b&1) r=r*a%MOD;
			a=a*a%MOD;
			b>>=1;
		}
		return r;
	}
	void NTT(int *a,int len,int op)
	{
		for(int i=0;i>1]>>1)|((len/2)*(i&1));
			if(i