前言

經典板子應用題

題目相關

鏈接

題目大意

現在有一個$n$個節點的樹，初始$n$個節點有$n?2$個是白色的，$2$個是黑色的
每次可以將一個黑點染紅，并將相鄰的白點同時染黑
問把整棵樹染紅的方法數，答案模$998244353$

數據范圍

$n\le 234567$

題解

兩個點的情況比較麻煩
我們先考慮一開始只有一個黑點的情況
我們把一開始的黑點當作根節點建樹
對于每一個節點$u$，設$u$節點及其子樹的大小為$siz{e}_u$，我們分析其子樹對答案的貢獻
其子樹肯定要選$u$節點本身
剩下的節點如果沒有限制，那么方案數為$(siz{e}_u?1)!$
然后我們考慮限制，我們發現每個子樹內部有其限制
那么總方案數為
$$an{s}_u=(siz{e}_u?1)!\prod _{f{a}_v=u}\frac{an{s}_v}{siz{e}_v!}$$
進行整理
$$an{s}_u=\frac{(siz{e}_u?1)!}{{\prod }_{f{a}_v=u}siz{e}_v!}\prod _{f{a}_v=u}an{s}_v$$
然后容易發現
$$\begin{array}{rl}an{s}_{root}& =\prod _{u=1}^n\frac{(siz{e}_u?1)!}{{\prod }_{f{a}_v=u}siz{e}_v!}\\ & =\frac{{\prod }_{u=1}^n(siz{e}_u?1)!}{{\prod }_{u=1,u?=root}^{n}siz{e}_u!}\\ & =(siz{e}_{root}?1)!\prod _{u=1,u?=root}^n\frac{(siz{e}_u?1)!}{siz{e}_u!}\\ & =(siz{e}_{root}?1)!\prod _{u=1,u?=root}^n\frac{1}{siz{e}_u}\\ & =siz{e}_{root}!\prod _{u=1}^n\frac{1}{siz{e}_u}\\ & =\frac{n!}{{\prod }_{u=1}^{n}siz{e}_u}\end{array}$$
然后考慮兩個點的情況
設初始的兩個黑點為$a,b$，我們新加一個點$s$，將$s$連向$a$和$b$，并且初始設為只有$s$為黑點，那么問題就轉化成環套樹上求答案
我們的思路是枚舉環上染紅的最后一個點的位置，但這樣并不能直接做
所以我們枚舉環上的邊并將其刪除使圖成為樹并計算答案
我們發現，這么計算會出現重復的情況，對于一個方案，我們找到這個方案在環上的最后被染紅的點，我們發現其被環上相鄰兩點染黑的情況各一次，即所有方案被算到兩次，所以答案要乘以$\frac{1}{2}$
對于非環上的點我們可以進行預處理，對于節點$s$也可以直接預處理，設這些點的$size$和為$Z$
對于一個環上的點$u$，設$a_u$為其所有的確定子樹大小，即一加所有非環上兒子的$size$，設$b_u$為對于某種斷環方式下其子樹的$size$
設$t$為某種斷環方式下的環上子樹大小和即$t=\sum b_u$
我們觀察一下$t$的取值情況
我們假設環上的點有$k+1$個，設$s$點編號為0，其余的點依次沿環編號為1 ~ k
假設斷的邊是i和i+1
我們發現其實$b$就是1 ~ i里的$a$的后綴和，i+1 ~ k里的$a$的前綴和
我們對$a$做一遍前綴和成為$c$，我們發現$\prod b={\prod }_{j?=i}|c_i?c_j|$（注意$c_0=0$）
將絕對值去掉（直接分類討論即可）后，問題就和多項式快速插值里的一樣了
摘一下結論：
設$R(x)={\prod }_{j=1}^n(x?x_j)$
$$\prod _{j=1,i?=j}^n(x_i?x_j)=R^{\prime }(x_i)$$
這樣的話多項式多點求值即可
復雜度$\mathcal{O}(nlo{g}^{2}n)$

代碼

本代碼使用了板子

#include<cstdio> #include<cctype> #include<cstring> #include<cstdlib> #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=2097152,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; } namespace Poly///namespace of Poly { int W_[maxn],ha[maxn],hb[maxn],Inv[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<<=1){const int WW=pow(3,(mod-1)/(i*2));W_[i]=1;for(rg int j=i+1,k=i<<1;j<k;j++)W_[j]=(ll)W_[j-1]*WW%mod;}Inv[0]=Inv[1]=1;for(rg int i=2;i<x;i++)Inv[i]=(ll)(mod-mod/i)*Inv[mod%i]%mod; } int L; inline void DFT(int*A)//prepare:init L {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)for(rg int j=0,J=i<<1;j<L;j+=J)for(rg int k=0;k<i;k++){const int x=A[j+k],y=(ll)A[j+k+i]*W_[i+k]%mod;A[j+k]=Md(x+y),A[j+k+i]=Md(mod+x-y);} } void IDFT(int*A) {for(rg int i=1;i<L-i;i++)swap(A[i],A[L-i]);DFT(A); } inline int Quadratic_residue(const int a) {if(a==0)return 0;int b=(rand()<<14^rand())%mod;while(pow(b,(mod-1)>>1)!=mod-1)b=(rand()<<14^rand())%mod;int s=mod-1,t=0,x,inv=pow(a,mod-2),f=1;while(!(s&1))s>>=1,t++,f<<=1;t--,x=pow(a,(s+1)>>1),f>>=1;while(t){f>>=1;if(pow((int)((ll)inv*x%mod*x%mod),f)!=1)x=(ll)x*pow(b,s)%mod;t--,s<<=1;}return min(x,mod-x); } struct poly {std::vector<int>A;poly(){A.resize(0);}poly(const int x){A.resize(1),A[0]=x;}inline int&operator[](const int x){return A[x];}inline int operator[](const int x)const{return A[x];}inline void clear(){A.clear();}inline unsigned int size()const{return A.size();}inline void resize(const unsigned int x){A.resize(x);}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()const{for(rg unsigned int i=0;i<A.size();i++)print(A[i]),putchar(' ');}inline poly operator +(const poly b)const{poly RES;RES.resize(max(size(),b.size()));for(rg unsigned int i=0;i<RES.size();i++)RES[i]=Md((i<size()?A[i]:0)+(i<b.size()?b[i]:0));return RES;}inline poly operator -(const poly b)const{poly RES;RES.resize(max(size(),b.size()));for(rg unsigned int i=0;i<RES.size();i++)RES[i]=Md((i<size()?A[i]:0)+mod-(i<b.size()?b[i]:0));return RES;}inline poly operator *(const int b)const{poly RES=*this;for(rg unsigned int i=0;i<RES.size();i++)RES[i]=(ll)RES[i]*b%mod;return RES;}inline poly operator /(const int b)const{poly RES=(*this)*pow(b,mod-2);return RES;}inline poly operator *(const poly b)const{const int RES=A.size()+b.size()-1;L=1;while(L<RES)L<<=1;poly c;c.A.resize(RES);memset(ha,0,L<<2);memset(hb,0,L<<2);for(rg unsigned int i=0;i<A.size();i++)ha[i]=A[i];for(rg unsigned int i=0;i<b.A.size();i++)hb[i]=b.A[i];DFT(ha),DFT(hb);for(rg int i=0;i<L;i++)ha[i]=(ll)ha[i]*hb[i]%mod;IDFT(ha);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;}inline poly inv()const{poly C;if(A.size()==1){C=*this;C[0]=pow(C[0],mod-2);return C;}C.resize((A.size()+1)>>1);for(rg unsigned int i=0;i<C.size();i++)C[i]=A[i];C=C.inv();L=1;while(L<(int)size()*2-1)L<<=1;for(rg unsigned int i=0;i<A.size();i++)ha[i]=A[i];for(rg unsigned int i=0;i<C.size();i++)hb[i]=C[i];memset(ha+A.size(),0,(L-A.size())<<2);memset(hb+C.size(),0,(L-C.size())<<2);DFT(ha),DFT(hb);for(rg int i=0;i<L;i++)ha[i]=(ll)(2-(ll)hb[i]*ha[i]%mod+mod)*hb[i]%mod;IDFT(ha);const int inv=pow(L,mod-2);C.resize(size());for(rg unsigned int i=0;i<size();i++)C[i]=(ll)ha[i]*inv%mod;return C;} /* inline poly inv()const{poly C;if(A.size()==1){C=*this;C[0]=pow(C[0],mod-2);return C;}C.resize((A.size()+1)>>1);for(rg unsigned int i=0;i<C.size();i++)C[i]=A[i];C=C.inv();poly D=(poly)2-*this*C;D.resize(size());D=D*C;D.resize(size());return D;}*///大常數版本 inline void Reverse(const int n){A.resize(n);for(rg int i=0,j=n-1;i<j;i++,j--)swap(A[i],A[j]);}inline poly operator /(const poly B)const{if(size()<B.size())return 0;poly a=*this,b=B;a.Reverse(size()),b.Reverse(B.size());b.resize(size()-B.size()+1);b=b.inv();b=b*a;b.Reverse(size()-B.size()+1);return b;}inline poly operator %(const poly B)const{poly C=(*this)-(*this)/B*B;C.resize(B.size()-1);return C;}inline poly diff()const{poly C;C.resize(size()-1);for(rg unsigned int i=1;i<size();i++)C[i-1]=(ll)A[i]*i%mod;return C;}inline poly inte()const{poly C;C.resize(size()+1);for(rg unsigned int i=0;i<size();i++)C[i+1]=(ll)A[i]*Inv[i+1]%mod;C[0]=0;return C;}inline poly ln()const{poly C=(diff()*inv()).inte();C.resize(size());return C;}inline poly exp()const{poly C;if(size()==1){C=*this;C[0]=1;return C;}C.resize((size()+1)>>1);for(rg unsigned int i=0;i<C.size();i++)C[i]=A[i];C=C.exp();C.resize(size());poly D=(poly)1-C.ln()+*this;D=D*C;D.resize(size());return D;}inline poly sqrt()const{poly C;if(size()==1){C=*this;C[0]=Quadratic_residue(C[0]);return C;}C.resize((size()+1)>>1);for(rg unsigned int i=0;i<C.size();i++)C[i]=A[i];C=C.sqrt();C.resize(size());C=(C+*this*C.inv())*(int)499122177;C.resize(size());return C;}inline poly operator >>(const unsigned int x)const{poly C;if(size()<x){C.resize(0);return C;}C.resize(size()-x);for(rg unsigned int i=0;i<C.size();i++)C[i]=A[i+x];return C;}inline poly operator <<(const unsigned int x)const{poly C;C.RE(size()+x);for(rg unsigned int i=0;i<size();i++)C[i+x]=A[i];return C;}inline poly Pow(const unsigned int x)const{for(rg unsigned int i=0;i<size();i++)if(A[i]){poly C=((((*this/A[i])>>i).ln()*x).exp()*pow(A[i],x))<<(min(i*x,size()));C.resize(size());return C;}return *this;}inline void cheng(const poly&B){for(rg unsigned int i=0;i<size();i++)A[i]=(ll)A[i]*B[i]%mod; }inline void jia(const poly&B){for(rg unsigned int i=0;i<size();i++)A[i]=Md(A[i]+B[i]); }inline void dft(){memset(ha,0,L<<2);for(rg unsigned int i=0;i<A.size();i++)ha[i]=A[i];DFT(ha);resize(L);for(rg int i=0;i<L;i++)A[i]=ha[i];}inline void idft(){memset(ha,0,L<<2);for(rg unsigned int i=0;i<A.size();i++)ha[i]=A[i];IDFT(ha);const int inv=pow(L,mod-2);for(rg int i=0;i<L;i++)A[i]=(ll)ha[i]*inv%mod;while(size()&&!A[size()-1])A.pop_back();} }; void fz(const int root,const int l,const int r,std::vector<int>&v,std::vector<poly>&A) {if(l==r){A[root].resize(2);A[root][0]=(mod-v[l])%mod;A[root][1]=1;return;}const int mid=(l+r)>>1;fz(root<<1,l,mid,v,A),fz(root<<1|1,mid+1,r,v,A);A[root]=A[root<<1]*A[root<<1|1]; } void calc(const int root,const int l,const int r,std::vector<int>&v,std::vector<poly>&A,std::vector<poly>&B) {if(l==r){v[l]=B[root][0];return;}const int mid=(l+r)>>1;B[root<<1]=B[root]%A[root<<1];B[root<<1|1]=B[root]%A[root<<1|1];calc(root<<1,l,mid,v,A,B),calc(root<<1|1,mid+1,r,v,A,B); } void multi_point_evaluation(const poly a,std::vector<int>&v) {std::vector<poly>A,B;A.resize(maxn),B.resize(maxn);fz(1,0,v.size()-1,v,A);B[1]=a%A[1];calc(1,0,v.size()-1,v,A,B); } void fz2(const int root,const int l,const int r,std::vector<int>&y,std::vector<poly>&A,std::vector<poly>&B) {if(l==r){B[root].resize(1),B[root][0]=y[l];return;}const int mid=(l+r)>>1;fz2(root<<1,l,mid,y,A,B),fz2(root<<1|1,mid+1,r,y,A,B);B[root]=B[root<<1]*A[root<<1|1]+B[root<<1|1]*A[root<<1]; } poly interpolation(std::vector<int>&x,std::vector<int>&y) {std::vector<poly>A,B;A.resize(maxn),B.resize(maxn);fz(1,0,x.size()-1,x,A);multi_point_evaluation(A[1].diff(),x);for(rg unsigned int i=0;i<x.size();i++)y[i]=(ll)y[i]*pow(x[i],mod-2)%mod;fz2(1,0,x.size()-1,y,A,B);return B[1]; } }///namespace of Poly int n,a,b; int head[maxn],nxt[maxn],tow[maxn],tmp,fa[maxn],size[maxn]; inline void addb(const int u,const int v) {tmp++;nxt[tmp]=head[u];head[u]=tmp;tow[tmp]=v; } void dfs1(const int u) {size[u]=1;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa[u])fa[v]=u,dfs1(v),size[u]+=size[v];} } int stack[maxn],top,c[maxn],Z,fac=1,ans;bool is[maxn]; std::vector<int>C; std::vector<Poly::poly>A; int main() {Poly::init(maxn);///namespace of Polyread(n),read(a),read(b);for(rg int i=1;i<n;i++){int u,v;read(u),read(v);addb(u,v),addb(v,u);}dfs1(a);while(b!=a)stack[++top]=b,is[b]=1,b=fa[b];stack[++top]=b,is[b]=1,b=fa[b];for(rg int i=1;i<=top;i++){const int u=stack[i];c[i]=1;for(rg int j=head[u];j;j=nxt[j]){const int v=tow[j];if(!is[v])c[i]+=size[v];}}Z=n+1;for(rg int i=1;i<=n;i++){fac=(ll)fac*i%mod;if(!is[i])Z=(ll)Z*size[i]%mod;}fac=(ll)fac*(n+1)%mod;C.push_back(0);for(rg int i=1;i<=top;i++)c[i]=Md(c[i]+c[i-1]),C.push_back(c[i]);A.resize(maxn);Poly::fz(1,0,top,C,A);Poly::multi_point_evaluation(A[1].diff(),C);for(rg int i=0;i<=top;i++)if((top-i)&1)ans=Md(ans+mod-(ll)fac*pow((ll)C[i]*Z%mod,mod-2)%mod);else ans=Md(ans+(ll)fac*pow((ll)C[i]*Z%mod,mod-2)%mod);print((ll)ans*499122177%mod);return flush(),0; }

總結

先是要講方案數通過類似遞歸式的形式寫出來然后化簡
然后用一個很好的加點思路
代碼的話差不多就是板子了

總結

以上是生活随笔為你收集整理的[loj6391][THUPC2018]淘米神的树（Tommy）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。