Min-Max容斥真好用

LOJ #2542

題意：給一棵不超過1818個節(jié)點(diǎn)的樹，50005000次詢問，每次問從根隨機(jī)游走走遍一個集合的期望步數(shù)

---

Solution:

考慮Min-Max容斥

有Max(S)=∑T?S(?1)|T|+1Min(T)

其中S,T是一個集合，Max(S)表示S中最大元素，Min(S)同理

我們設(shè)集合S表示走到每個點(diǎn)的期望時間

顯然走遍一個集合的期望時間就是Max(S)

且第一次走到某集合的期望時間是Min(S)

Max(S)不容易計(jì)算，我們轉(zhuǎn)而求解Min(S)

令fi表示從點(diǎn)i隨機(jī)游走第一次走到集合SS的期望步數(shù)

這個顯然可以高斯消元，不過復(fù)雜度略大

由于轉(zhuǎn)移是在樹上，可以直接在樹上O(n)消元

我們令fi=ki?f?fa[i]+bi

當(dāng)ii在集合S中的時候ki=bi=0否則進(jìn)行轉(zhuǎn)移

轉(zhuǎn)移的時候把當(dāng)前點(diǎn)孩子的k和b算出然后代到當(dāng)前點(diǎn)的方程中算出當(dāng)前點(diǎn)的k和b

這樣可以在O(2n?n?算逆元復(fù)雜度)的時間復(fù)雜度內(nèi)算出所有的Min(S)

?

然后直接容斥算Max(S),復(fù)雜度是5000?2n的

我們可以提前預(yù)處理每個Max(S)每次枚舉子集轉(zhuǎn)移，時間復(fù)雜度是3^n的

據(jù)說都能過

不過其實(shí)這部分可以優(yōu)化到2n?n的

我們直接根據(jù)popcount(S)的奇偶性來判斷是否給Min(S)乘上?1

然后直接高維前綴和即可

#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define mod 998244353 #define ll long long using namespace std; struct ret{int k,b;ret operator +(const ret s)const{return {(k+s.k)%mod,(b+s.b)%mod};}ret operator *(const int s)const{return {(ll)k*s%mod,1ll*b*s%mod};} }f[19][1<<18]; const int N=50; int i,j,k,m,n,x,z,cnt,root,Q; int g[N],l[N],c[N],a[N],d[N],inv[N],Min[1<<18]; void add(int x,int y){a[++k]=y;if (!g[x]) g[x]=k;else c[l[x]]=k;l[x]=k; } int pow(int x,int y){int ans=1;for (int i=y;i;i>>=1,x=(ll)x*x%mod)if (i&1) ans=(ll)x*ans%mod;;return (ans+mod)%mod; } ret dfs(int x,int pre,int s){if (s>>x-1&1) return{0,0}; ret now={0,0};for (int i=g[x];i;i=c[i])if (a[i]!=pre) now=now+dfs(a[i],x,s)*inv[d[x]];const int Inv=pow(1-now.k,mod-2);return {(ll)Inv*inv[d[x]]%mod,1ll*Inv*(now.b+1)%mod}; } int main(){scanf("%d",&n);scanf("%d%d",&Q,&root);inv[0]=inv[1]=1;for (int i=2;i<=18;i++) inv[i]=(ll)inv[mod%i]*(mod-mod/i)%mod;for (int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);d[u]++;d[v]++;}for (int i=1;i<(1<<n);i++){ret ans=dfs(root,root,i);Min[i]=ans.b*(__builtin_popcount(i)&1?1:-1);}for (int i=0;i<n;i++)for (int j=0;j<1<<n;j++)if (j>>i&1) (Min[j]+=Min[j^(1<<i)])%=mod;while (Q--){int sum=0;scanf("%d",&x);for(int i=1;i<=x;i++) {int y;scanf("%d",&y);sum|=(1<<y-1);}printf("%d\n",(Min[sum]+mod)%mod);}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/zzrblogs/p/11196464.html

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

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

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