Loj #2541. 「PKUWC2018」猎人杀

好巧妙的题！

游戏过程中，概率的分母一直在变化，所以就非常的不可做。

所以我们将问题转化一下：我们可以重复选择相同的猎人，只不过在一个猎人被选择了过后我们就给他打上标记，再次选择他的时候就无效。这样与原问题是等价的。

证明：

设\(sum=\sum_iw_i,kill=\sum_{i被杀死了}w_i\)。

攻击到未被杀死的猎人\(i\)的概率为\(P\)。

则根据题意\(P=\frac{w_i}{sum-kill}\)。

问题转化后：

\[ \\P=\frac{kill}{sum}P+\frac{w_i}{sum}\\ \Rightarrow P=\frac{w_i}{sum-kill}。 \]

然后我们考虑容斥：枚举集合\(T\)中的猎人一定在\(1\)之后被杀死，其他猎人随意。

我们设\(S=\sum_{i\in T}w_i\)

则：

\[ \displaystyle \begin{align} ans&=(-1)^{|T|}\sum_{i=0}^{\infty}(1-\frac{S+w_1}{sum})^i\frac{w_1}{sum} \\&=(-1)^{|T|}\frac{1}{1-(1-\frac{S+w_1}{sum})}\frac{w_1}{sum} \\&=(-1)^{|T|}\frac{w_1}{w_1+S} \end{align} \]

然后我们就可以用背包背出所有\(\sum w_i\)恰好为\(S\)的带上容斥系数的方案数。

但复杂度有点高，于是我们考虑用生成函数来优化。这道题的生成函数还是比较简单，就是\(\Pi (1-x^{w_i})\)。用分治\(NTT\)实现。

代码：

#include
    
     #define ll long long#define mod 998244353#define N 100005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}ll ksm(ll t,ll x)  {    ll ans=1;    for(;x;x>>=1,t=t*t%mod)        if(x&1) ans=ans*t%mod;    return ans;}int rev[N<<2];void NTT(ll *a,int d,int flag) {    static ll G=3;    int n=1<
     
      >1]>>1)|((i&1)<
      
       >1;        ll w=flag==1?ksm(G,(mod-1)/len):ksm(G,mod-1-(mod-1)/len);        for(int i=0;i
       
        >1;        if(sum[mid]-sum[lx-1]<=sum[rx]-sum[mid]) l=mid;        else r=mid-1;    }    return l;}void solve(int l,int r,ll *f) {    if(l==r) {        f[0]=1;        f[w[l]]=mod-1;        return ;    }    int mid=binary(l,r);    const int d=ceil(log2(sum[r]-sum[l-1]))+1;    ll *a=new ll[(1<