https://www.zybuluo.com/ysner/note/1248507
题面
给定一棵(n)个结点的树,你从点(x)出发,每次等概率随机选择一条与所在点相邻的边走过去。
有(Q)次询问,每次询问给定一个集合(S),求如果从(x)出发一直随机游走,直到点集(S)中所有点都至少经过一次的话,期望游走几步。
特别地,点(x)(即起点)视为一开始就被经过了一次。
- (nleq18,Qleq5000)
解析
咦?(nleq18)?我会状压!
咦?所有点都至少经过一次?求期望?我会(Min-Max)容斥!
以上为看题想法
还记得[HNOI2013]游走吧?
在那一道题中,由于转移具有后效性,我们只能用解方程来求出到每个点的概率。
但这里是一颗树!转移没有后效性。
于是可以像(dp)一般转移结果。
设(f[i])表示到达第一次到达(i)号点的期望次数。
先列一个基本的期望转移式:((d[u])表示(u)号点的度数,(v)为(u)点的儿子)
[f[u]=frac{1}{d[u]}(f[fa]+1+sum_{vin son}(f[v]+1))
]
[f[u]=frac{1}{d[u]}f[fa]+frac{1}{d[u]}sum_{vin son}f[v]+1
]
根据套路,树上期望问题中,到点(u)的期望次数可以表示为(f[u]=A*f[fa]+B)。
依此继续化式子:
[f[u]=frac{1}{d[u]}f[fa]+frac{1}{d[u]}sum_{vin son}(A[v]*f[u]+B[v])+1
]
[(1-frac{A[v]}{d[u]})f[u]=frac{1}{d[u]}f[fa]+frac{1}{d[u]}sum_{vin son}B[v]+1
]
[(d[u]-A[v])f[u]=f[fa]+sum_{vin son}B[v]+d[u]
]
[f[u]=frac{1}{d[u]-A[v]}f[fa]+frac{sum_{vin son}B[v]+d[u]}{d[u]-A[v]}
]
则$$A=frac{1}{d[u]-A[v]}$$$$B=frac{sum_{vin son}B[v]+d[u]}{d[u]-A[v]}$$
枚举所有(S),按上述式子转移。一旦遇到集合内的数,(A[u]=B[u]=0)并(return)。
这样就可得到所有的(E(min(S)))。
然后(Min-Max)容斥就只要用个结论:
[E(max(S))=sum_{S'in S}E(min(S'))*(-1)^{|S'|+1}
]
复杂度(O(2^nn))。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=998244353,N=20;
struct Edge{int to,nxt;}e[N<<1];
int n,Q,rt,h[N],cnt,a[N],k,mx,q[N],d[N];
ll A[N],B[N],ans,res[(int)(2e6+100)];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;++d[u];}
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il ll ksm(re ll S,re ll o)
{
re ll T=S;S=1;
while(o)
{
if(o&1) S=S*T%mod;
T=T*T%mod;
o>>=1;
}
return S;
}
il void dfs(re int u,re int fa,re int S)
{
if((1<<u-1)&S) {A[u]=B[u]=0;return;}
re ll a=0,b=0;
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(v==fa) continue;
dfs(v,u,S);
(a+=A[v])%=mod;(b+=B[v])%=mod;
}
re ll ysn=ksm((d[u]-a+mod)%mod,mod-2);
A[u]=ysn;
B[u]=(d[u]+b)*ysn%mod;
}
il void Min_Max(re int x,re int sz,re int S)
{
if(x>k)
{
if(sz&1) (ans+=res[S])%=mod;
else ans=(ans+mod-res[S])%mod;
return;
}
Min_Max(x+1,sz,S);
Min_Max(x+1,sz+1,S|(1<<q[x]-1));
}
int main()
{
memset(h,-1,sizeof(h));
n=gi();Q=gi();rt=gi();mx=(1<<n)-1;
fp(i,1,n-1)
{
re int u=gi(),v=gi();
add(u,v);add(v,u);
}
fp(S,1,mx)
{
fp(i,1,n) A[i]=B[i]=0;
dfs(rt,0,S);
res[S]=B[rt];
}
while(Q--)
{
k=gi();ans=0;
fp(i,1,k) q[i]=gi();
Min_Max(1,0,0);
printf("%lld
",ans);
}
return 0;
}