前言

先是容斥
分治套NTT

題意簡介

題目鏈接

題目大意

現(xiàn)在有$n$個獵人，每個獵人都有一個值$w_i$
進行$n$次殺人，死掉的人不會再被殺
每次殺人過程中第$i$個獵人被殺的概率為$\frac{w_i}{\sum w_j}$
問第一個獵人最后一個死的概率
（答案對998244353取模）

數(shù)據(jù)范圍

$w_i>0,1\le \sum w\le 100000$
由于上面這兩個限制，我們發(fā)現(xiàn)$1\le n\le 100000$

題解

我們要求的是沒有人在$1$號獵人后死的概率
我們發(fā)現(xiàn)直接求不好求，那么考慮容斥
設(shè)$f(S)$為$S$集合內(nèi)的人全都在$1$號獵人后死的概率（不在$S$集合里的人不確定）
顯然$f(S)=\frac{w_1}{{\sum }_{i\in S}{w}_i+w_1}$
根據(jù)容斥的定義式
$$|A_1\cup A_2\cup ...\cup A_n|=\sum _{i=1}^n(?1{)}^{i?1}\sum _{|T|=i,T=\{x_1...x_i\}}|A_{x_1}\cap A_{x_2}\cap ...\cap A_{x_i}|$$
我們發(fā)現(xiàn)我們要求的就是$$\sum _{|T|=i,T=\{x_1...x_i\}}(?1{)}^{i}f(T)$$
我們發(fā)現(xiàn)，直接枚舉所有集合復(fù)雜度為$\mathcal{O}(2^n)$，顯然不能接受

---

這題在數(shù)據(jù)范圍上是對$\sum w$進行限制的，所以不能學傻
我們可以得到一個非常通俗易懂的$\mathcal{O}(n^2)$DP算法
我們可以用$f_{i,j}$表示前$i$個獵人，$\sum w=j$的方案數(shù)（差不多就是背包）
轉(zhuǎn)移是枚舉下一個元素是否選，是$\mathcal{O}(1)$的
由于奇偶性不同的情況下符號不一樣，所以我們在轉(zhuǎn)移的時候可以使用$?1$的系數(shù)，這樣就可以統(tǒng)計答案了
這個$\mathcal{O}(n^2)$算法期望得分50分

---

考慮生成函數(shù)，我們就會發(fā)現(xiàn)（生成函數(shù)基礎(chǔ)應(yīng)用）
本質(zhì)上這個$dp$就是一個多項式，每次卷上一個在$w_i$位上有個$?1$，$0$位上有個$1$的多項式
知道結(jié)果多項式即可
成功將復(fù)雜度升至$\mathcal{O}(n^{2}logn)$
我們發(fā)現(xiàn)，多項式乘法的復(fù)雜度拆開成兩個多項式長度可以表示為$\mathcal{O}((lena+lenb)log(lena+lenb))$
直接分治即可
具體做法的代碼（縮略版，其實是我不知道寫偽代碼的正確姿勢）

polynomial calc(int l,int r) {if(l==r)return a[l];int mid=(l+r)/2;return calc(l,mid)*calc(mid+1,r); }

將復(fù)雜度降到$\mathcal{O}(nlo{g}^{2}n)$
證明： $log(lena+lenb)?logn$(這里的$n$為100000)
每個多項式只會參與多項式乘法$logn$次，一次的復(fù)雜度消耗為長度乘以log
故總復(fù)雜度為$\mathcal{O}(nlo{g}^{2}n)$

代碼

#include<cstdio> #include<cctype> #include<cstring> #include<vector> namespace fast_IO {const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);} } using namespace fast_IO; #define getchar() getchar_() #define putchar(x) putchar_((x)) typedef long long ll; #define rg register template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline T mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline T maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline void swap(T*a,T*b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } const int maxn=2097153,mod=998244353; inline int Md(const int x){return x>=mod?x-mod:x;} template<typename T> inline int pow(int x,T y) {rg int res=1;x%=mod;for(;y;y>>=1,x=(ll)x*x%mod)if(y&1)res=(ll)res*x%mod;return res; } int W_[maxn],FW_[maxn],ha[maxn],hb[maxn]; inline void init(const int x) {rg int tim=0,lenth=1;while(lenth<x)lenth<<=1,tim++;for(rg int i=1;i<lenth;i++){W_[i]=pow(3,(mod-1)/i/2);FW_[i]=pow(W_[i],mod-2);} } int L; inline void NTT(int*A,const int fla) {for(rg int i=0,j=0;i<L;i++){if(i>j)swap(A[i],A[j]);for(rg int k=L>>1;(j^=k)<k;k>>=1);}for(rg int i=1;i<L;i<<=1){const int w=fla==-1?FW_[i]:W_[i];for(rg int j=0,J=i<<1;j<L;j+=J){int K=1;for(rg int k=0;k<i;k++,K=(ll)K*w%mod){const int x=A[j+k],y=(ll)A[j+k+i]*K%mod;A[j+k]=Md(x+y),A[j+k+i]=Md(mod+x-y);}}} } struct poly {std::vector<int>A;inline int&operator[](const int x){return A[x];}inline void clear(){A.clear();}inline unsigned int size(){return A.size();}void RE(const int x){A.resize(x);for(rg int i=0;i<x;i++)A[i]=0; }void readin(const int MAX){A.resize(MAX);for(rg int i=0;i<MAX;i++)read(A[i]);}void putout(){for(rg int i=0;i<A.size();i++)print(A[i]),putchar(' ');}inline poly operator *(const poly b)const{L=1;const int RES=A.size()+b.A.size()-1;while(L<RES)L<<=1;poly c;c.A.resize(RES);memset(ha,0,sizeof(int)*L);memset(hb,0,sizeof(int)*L);for(rg int i=0;i<A.size();i++)ha[i]=A[i];for(rg int i=0;i<b.A.size();i++)hb[i]=b.A[i];NTT(ha,1),NTT(hb,1);for(rg int i=0;i<L;i++)ha[i]=(ll)ha[i]*hb[i]%mod;NTT(ha,-1);const int inv=pow(L,mod-2);for(rg int i=0;i<RES;i++)c.A[i]=(ll)ha[i]*inv%mod;return c;} }a[100001]; int n,w[100001]; void fz(const int l,const int r) {if(l==r){a[l].RE(w[l]+1);a[l][0]=1;a[l][w[l]]=mod-1;return;}const int mid=(l+r)>>1;fz(l,mid),fz(mid+1,r);a[l]=a[l]*a[mid+1];a[mid+1].A.clear(); } int ans; int main() {init(maxn-2); read(n);for(rg int i=0;i<n;i++)read(w[i]);fz(1,n-1);for(rg int i=0;i<a[1].size();i++)ans=Md(ans+(ll)w[0]*pow(i+w[0],mod-2)%mod*a[1][i]%mod);print(ans);return flush(),0; }

總結(jié)

寫了一個多項式乘法的板子（還沒填更多的功能），剩下的就比較清真了
終于有一篇博客寫到分治+FFT了
想到容斥就有50分，去年的我50分都沒

總結(jié)

以上是生活随笔為你收集整理的[PKUWC2018][loj2541]猎人杀的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。