前言

這是學習容斥過程中的一個比較裸的題了

題意簡介

題目鏈接

題目大意

給出一棵$n$個點的樹，給出樹上的一個點$x$
現(xiàn)在進行$Q$次詢問，每次詢問一個點集，求從$x$點開始進行隨機隨機游走，第一次走遍這個點集的期望步數(shù)
(隨機游走即每次等概率走到一個與自己相鄰的點)

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

$1\le n\le 18,1\le Q\le 5000$

前置知識（最值反演 Min-Max容斥）

$$max\{S\}=\sum _{T?S}(?1{)}^{|T|+1}min\{T\}$$
具體介紹可以看我的博客
介紹鏈接
這個式子套上期望依然成立

題解

所有點第一次期望訪問的步數(shù)的集合$S$，$max\{S\}$就是每個點都被走過的期望步數(shù)，$min\{S\}$代表里任意一個點被第一次訪問的期望時間
我們發(fā)現(xiàn)我們現(xiàn)在要求的就是$max\{S\}$
但是直接求不好求，所以用Min-Max容斥轉(zhuǎn)化成求$min\{S\}$
我們可以預處理$min\{S\}$，并且$\Theta (3^n)$枚舉子集計算答案
那么現(xiàn)在就是考慮如何求$min\{S\}$
這個似乎我當時在考場上就推出來了
考慮對于一個集合$S$，設(shè)$f(x)$為從$x$點開始隨機游第一次訪問集合$S$的期望步數(shù)
然后分類討論
若$x\in S$
$$f(x)=0$$
若$x\in /S$
$$f(x)=1+\frac{1}{d_x}\sum _{edge(x,y)}f(y)$$
其中$d_x$為$x$的度數(shù)，$edge(x,y)$代表$x,y$間有邊
對于$x\in /S$的部分隨便定一個根$root\in S$
我們發(fā)現(xiàn)對于$x$是葉子節(jié)點的情況：$$f(x)=f(f{a}_x)+1$$
我們發(fā)現(xiàn)對于$x$是非子節(jié)點的情況：$$f(x)=1+\frac{1}{d_x}\sum _{y=so{n}_x}f(y)+\frac{1}{d_x}f(f{a}_x)$$
我們設(shè)一個節(jié)點$x$的答案為$(a,b)$代表：$$f(x)=a+bf(f{a}_x)$$
我們發(fā)現(xiàn)，對于任何一個節(jié)點的答案$(a,b)$，一定滿足$b\le 1$（實數(shù)意義下）
（由于$root\in S$，所以不會有枚舉的節(jié)點沒有$fa$的情況）
所以對于非葉子節(jié)點的$x$，等號右側(cè)的$f(x)$的系數(shù)一定小于$1$，一項即可算出當前的的答案$(a,b)$
算完答案$(a,b)$后，即可從根倒著推回去
非常方便
這樣算出來復雜度是$\Theta (3^n)$的，需要卡常，我寫了一波被卡成70
這個時候就需要優(yōu)化瓶頸
發(fā)現(xiàn)是裸的FMT，寫一發(fā)就好了
復雜度$\Theta (2^{n}nlogn)$

代碼

#include<cstdio> #include<cctype> 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)) //#include<ctime> #define rg register typedef long long LL; 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 void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void 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 lcm(const T a,const T b){return a/gcd(a,b)*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> inline 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 LL mod=998244353; inline LL pow(LL x,LL y) {LL res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res; } int n,q,x,k; int bit[20],inv[20],d[20]; int head[20],nxt[40],tow[40],tmp; inline void addb(const int u,const int v) {tmp++;nxt[tmp]=head[u];head[u]=tmp;tow[tmp]=v; } int zt; struct Ans {int a,b;inline Ans operator +(const Ans&y)const{return (Ans){a+y.a,b+y.b};} }Q[20]; LL ans[20]; void dfs1(const int u,const int fa) {if(zt&bit[u]){for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;dfs1(v,u);}Q[u].a=Q[u].b=0;}else{const LL INV=inv[d[u]];Q[u]=(Ans){1,INV};LL xs=1;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;dfs1(v,u);xs=(xs+mod-INV*Q[v].b%mod)%mod;Q[u].a=(Q[u].a+Q[v].a*INV)%mod;}const LL INTO=pow(xs,mod-2);Q[u].a=INTO*Q[u].a%mod;Q[u].b=INTO*Q[u].b%mod;} } void dfs2(const int u,const int fa) {if(zt&bit[u]){ans[u]=0;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;dfs2(v,u);}}else{ans[u]=(Q[u].a+ans[fa]*Q[u].b)%mod;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v==fa)continue;dfs2(v,u);}} } int res[524288]; int pc[524288]; int main() {bit[1]=1;for(rg int i=2;i<=19;i++)bit[i]=bit[i-1]<<1;inv[1]=1;for(rg int i=2;i<=19;i++)inv[i]=(LL)(mod-mod/i)*inv[mod%i]%mod;read(n),read(q),read(x);for(rg int i=1;i<n;i++){int u,v;read(u),read(v);addb(u,v),addb(v,u);d[u]++,d[v]++;}for(zt=1;zt<bit[n+1];zt++){pc[zt]=pc[zt>>1]^(zt&1);for(rg int i=1;i<=n;i++)if(zt&bit[i]){dfs1(i,i);dfs2(i,i);break;}if(pc[zt]&1)res[zt]=ans[x];else res[zt]=(mod-ans[x])%mod;}for(rg int i=1;i<bit[n+1];i<<=1)for(rg int j=0;j<bit[n+1];j++)if(i&j)res[j]=(res[j]+res[j^i])%mod;while(q--){read(k),zt=0;while(k--)read(x),zt|=bit[x];print(res[zt]),putchar('\n');}return flush(),0; }

不知為何分類討論使得程序拉的特別長

總結(jié)

min-max容斥很重要，使得整題好做了很多
然后這算是FMT的應(yīng)用吧，清真好題

總結(jié)

以上是生活随笔為你收集整理的最值反演[PKUWC2018][loj2542]随机游走的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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