题目：https://loj.ac/problem/2541
看了题解才会……有三点很巧妙。
1.分母如果变动，就很不好。所以考虑把操作改成 “已经选过的人仍然按 \( w_i \) 的概率被选，但是再次选中一个已经选过的人算作没有操作” 。
2.然后要容斥，考虑强制点集 S 的人在 1 号点之后被选、其余随意，那么
\( ans=\sum\limits_{S} (-1)^{|S|} \sum\limits_{i=0}^{\infty} (1-\frac{w_1 + w_S}{A})^i \frac{w_1}{A} \)
（其中 A 表示 \( \sum\limits_{i=1}^{n} w_i \) ，\( w_S \) 表示 \( \sum\limits_{i \in S} w_i \) ）
等比数列求和一下，就是 \( ans=\sum\limits_{S} (-1)^{|S|} \frac{w_1}{w_1+w_S} \)
3.注意到 \( \sum w <=1e5 \) ，所以考虑把那个式子里的分母看做多项式的次数！
那么算一个 \( \prod\limits_{i=2}^{n} (1-x^{w_i}) \)（这是考虑选出一个点集 S 的过程）
然后就是取 \( x^i \) 的系数 \( a_i \) ，给答案贡献 \( \frac{a_i}{w_1+i} \) ，最后答案再乘一个 \( w_1 \) 。
算那个连乘的式子，可以普通地分治。但注意到含有 k 个 w 的乘积式子的次数不是 k ，所以复杂度不是 \( T(n)=T(n/2)+O(nlogn) \) 。（可能是 n2logn？）
反正把 w 排个序再做就能了。不知道不排序是否也可以。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define vi vector<int> #define ll long long using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)fx=0;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)ret=ret*10+ch-‘0‘,ch=getchar(); return fx?ret:-ret; } const int N=1e5+5,M=(1<<17)+5,mod=998244353; int upt(int x){while(x>=mod)x-=mod;while(x<0)x+=mod;return x;} int pw(int x,int k) {int ret=1;while(k){if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;} int n,w[N],len,r[M],wn[M],wn2[M],inv[M]; void ntt_pre(int n) { for(len=1;len<=n;len<<=1); for(int R=2;R<=len;R<<=1) { wn[R]=pw(3,(mod-1)/R); wn2[R]=pw(3,(mod-1)-(mod-1)/R); inv[R]=pw(R,mod-2); } } void ntt(vi &a,bool fx) { for(int i=0;i<len;i++) if(i<r[i])swap(a[i],a[r[i]]); for(int R=2;R<=len;R<<=1) { int Wn=fx?wn2[R]:wn[R]; for(int i=0,m=R>>1;i<len;i+=R) for(int j=0,w=1;j<m;j++,w=(ll)w*Wn%mod) { int x=a[i+j],y=(ll)w*a[i+m+j]%mod; a[i+j]=upt(x+y); a[i+m+j]=upt(x-y); } } if(!fx)return; int iv=inv[len]; for(int i=0;i<len;i++)a[i]=(ll)a[i]*iv%mod; } vi solve(int L,int R) { if(L==R) { vi ret; ret.resize(w[L]+1); ret[0]=1; ret[w[L]]=-1; return ret; } int mid=L+R>>1; vi a=solve(L,mid), b=solve(mid+1,R); int lm=a.size()-1+b.size()-1; for(len=1;len<=lm;len<<=1); for(int i=0,j=len>>1;i<len;i++) r[i]=(r[i>>1]>>1)+((i&1)?j:0); a.resize(len); b.resize(len); ntt(a,0); ntt(b,0); for(int i=0;i<len;i++)a[i]=(ll)a[i]*b[i]%mod; ntt(a,1); a.resize(lm+1); return a; } int main() { n=rdn(); int sm=0; for(int i=1;i<=n;i++) { w[i]=rdn(); if(i>1)sm+=w[i];}//if!!! ntt_pre(sm); sort(w+2,w+n+1);// vi f=solve(2,n); int ans=0; for(int i=0;i<=sm;i++) if(f[i])ans=(ans+(ll)f[i]*pw(upt(w[1]+i),mod-2))%mod; ans=(ll)ans*w[1]%mod; printf("%d\n",ans); return 0; }
LOJ 2541 「PKUWC2018」猎人杀——思路+概率+容斥+分治
原文：https://www.cnblogs.com/Narh/p/10886569.html