• 题解

  • 题目中的选择条件等价于正常选择所有猎人，而如果选到已经出局的猎人就继续选；
  • 这两种选法是一样的因为(设$W=\sum_{i=1}^{n}w_{i}$ , $X$为已经出局的猎人的$w$之和)：
  • $P_{i} = \sum_{i=0}^{ \infty } {(\frac{X}{W})}^i \frac{w_{i}}{W}$
  •  $= \frac{w_{i}}{W} \sum_{i=0}^{ \infty } {(\frac{X}{W})}^i$
  • $ = \frac{w_{i}}{W} \frac{1}{1-\frac{X}{W}}$
  • $ = \frac{w_{i}}{W-X} $
  • 考虑枚举强制$S$集合$(1 \notin S)$中的人在1之后出局，设$X(S) = \sum_{i=2}^{n} [i \in S]w_{i}$；
  •  $ans = \sum_{S} {(-1)}^{|S|}  \sum_{i=0}^{ \infty }  (1-\frac{w_{1}+X(S)}{W})^i  \frac{w_{1}}{W} $
  • $ans  = \sum_{S} {(-1)}^{|S|} \frac{w_{1}}{w_{1}+X(S)} $
  • 考虑求这个式子：
  • $ans = \sum_{i=0}^{W} \frac{w_{1}}{w_{1}+i} \sum_{S} [X(S)==i] (-1)^{|S|}$
  • 用生成函数$\Pi_{i=2}^{n} (1-x^{w_{i}})$处理处后面的部分即可；
  • 时间复杂度：$O(Wlog^2 \ W)$

1 #include
      
        2 #define mod 998244353 3 using namespace std; 4 const int N=200010,M=20; 5 int n,m,w[N],f[M][N],mx[M],L,len,sz,Wn[M][N],rev[N]; 6 char gc(){ 7     static char*p1,*p2,s[1000000]; 8     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); 9     return(p1==p2)?EOF:*p1++;10 }11 int rd(){12     int x=0;char c=gc();13     while(c<'0'||c>'9')c=gc();14     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();15     return x;16 }17 int pw(int x,int y){18     int re=1;19     for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)re=1ll*re*x%mod;20     return re;21 }22 void ntt(int*a,int f){23     for(int i=0;i
       
        
         >1;47     solve(l,mid),solve(mid+1,r);48     int a=sz-1,b=sz;49     m=mx[a]+mx[b];50     for(L=0,len=1;len<=m;len<<=1,L++);51     for(int i=1;i
         
          >1]>>1)|((i&1)<<(L-1));52     for(int i=mx[a]+1;i
          
           >=1){67         Wn[0][i]=pw(3,(mod-1)/i);68         Wn[1][i]=pw(Wn[0][i],mod-2);69     }70     solve(2,n);71     int ans=0;72     for(int i=0;i<=mx[1];++i){73         ans=(ans + 1ll*f[1][i]*w[1]%mod*pw(i+w[1],mod-2)%mod)%mod;74     }75     cout<<(ans+mod)%mod<