LOJ2541「PKUWC2018」猎人杀（分治+容斥原理+FFT/NTT）

传送门：https://loj.ac/problem/2541

$solution$:
直接算不好算
考虑容斥
转化一下问题，假如一个人死了之后不是真正死了，每当打到这些人后就重新开枪，这样的问题是等价的
我们枚举在1后面死的人的集合$T$,假设${\sum }_{i=1}^n{w}_i=S,{\sum }_{i\in T}{w}_i=A$ 那么此时的贡献（1死的概率）$P$的式子：

$$P=\sum _{i=1}^{\infty }(1-\frac{A+w_1}{S}{)}^i\ast \frac{w_1}{S}$$
$$=\frac{w_1}{S}\ast (\frac{1}{1-1+\frac{A+w_1}{S}})$$
$$=\frac{w_1}{A+w_1}$$
那么$ans={\sum }_S(-1{)}^{|S|}\frac{w_1}{sum(s)+w_1}$
对于$sum(S)$想同的不同的集合，我们可以放在一起算，问题就是怎么算容斥系数的和
可以发现$sum(S)$对应的系数就是$\prod (1-w_i)$的第$sum(S)$次系数
分治$NTT$即可
复杂度$O(nlo{g}^{2}n)$

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back 
#define pc putchar
#define mp make_pair
#define file(k) memset(k,0,sizeof(k))
#define ll long long

const int g = 3;
const int p = 998244353;
const int NUM = 22;

int n , m , N;
int a[20][4001000] , b[4001000];
int s[1001000];
int w[1001000]; 
int R[4001000] , flen;
int calc(int a,int b){return ((a+b)%p+p)%p;}
int del(int a,int b){return ((a-b)%p+p)%p;}
int mul(int a,int b){return 1ll*a*b%p;}

int ksm(int a, int b)  
{  
    int ans = 1;  
    a %= p;  
    while(b) {  
        if(b & 1)    
            ans = 1ll * ans * a % p;
        b >>= 1;  
        a = 1ll * a * a % p;  
    } 
    return ans%p;  
}  
void ntt(int *a ,int f){
    for(int i = 0; i < flen; ++i)
		if(i < R[i]) swap(a[i], a[R[i]]);
    for(int len = 2;len <= flen;len *= 2){
    	int wn = ksm( g , (p - 1) / len );
    	if(f == -1) wn = ksm(wn , p-2);
    	for(int k = 0;k <= flen / len - 1;++k){
    		int st = k * len;
    		ll w = 1;
    		for(int i = 0;i < len / 2;++i){
    			int x = a[st + i] % p,
    			   y = 1ll * (a[st + i + len / 2] % p) * w % p;
    		    a[st + i] = calc(x,y);
    		    a[st + i + len / 2] = del(x,y);
    		    w = 1ll * w * wn % p;
			}
    	}
      	
    } 
    if(f == -1){
    	int inv = ksm(flen , p-2);
    	for(int i = 0;i < flen ;++i)
    	  a[i] = 1ll * a[i] * inv % p;
    }
 	return;
}	
int rd()
{
    int sum = 0;char c = getchar();bool flag = true;
    while(c < '0' || c > '9') {if(c == '-') flag = false;c = getchar();}
    while(c >= '0' && c <= '9') sum = sum * 10 + c - 48,c = getchar();
    if(flag) return sum;
    else return -sum;
}
void solve(int l,int r,int d)
{
	if(l == r)
	{
		a[d][0] = 1;a[d][w[l]] = p-1;
		rep(i,1,w[l]-1) a[d][i] = 0; 
		return;
	}
	int mid = (l+r)>>1;
	solve(l,mid,d+1);
	rep(i,0,s[mid]-s[l-1]) a[d][i] = a[d+1][i];
	solve(mid+1,r,d+1);
	flen = 1;n = s[mid] - s[l-1];m = s[r]-s[mid];
	while(flen < (n+m+1)) flen <<= 1;
	rep(i,n+1,flen-1) a[d][i] = 0;
	rep(i,m+1,flen-1) a[d+1][i] = 0;
	int L = log2(flen);
	for(int i = 0;i < flen;++i)
	{
	 	R[i] = R[i>>1]>>1;
	 	if(i & 1) R[i] |= 1<<(L-1);
    }	
    ntt(a[d],1);ntt(a[d+1],1);
	rep(i,0,flen-1) a[d][i] = mul(a[d][i],a[d+1][i]);
	ntt(a[d],-1);
}
int main()
{
	N = rd();rep(i,1,N) w[i] = rd(),s[i] = s[i-1]+w[i];
	solve(2,N,0);
	int ans = 0;
	rep(S,0,s[N]-s[1]) ans = calc(ans,mul(w[1],mul( ksm(calc(S,w[1]),p-2) , a[0][S] ) ));
	printf("%dn",ans);
    return 0;
}

最后

以上就是无私秀发为你收集整理的LOJ2541「PKUWC2018」猎人杀（分治+容斥原理+FFT/NTT）的全部内容，希望文章能够帮你解决LOJ2541「PKUWC2018」猎人杀（分治+容斥原理+FFT/NTT）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。