传送门
题意
给定一个有根树,q次询问,每次询问给定树上点的一个集合S,求从根出发随机游走(根视为已经经过),经过S的所有点需要的期望次数,模998244353
1≤n≤18,1≤q≤5000
Solution
题目要求东西即为(Ei为从根游走到i的期望次数)
i∈SmaxEi
根据Min-Max 容斥
,可以转换成
i∈SmaxEi=T∈S∑(−1)∣T∣−1×i∈TminEi
设(−1)∣T∣−1×mini∈TEi为fi,表示从根出发经过T至少一个点的期望,暂时记fi为后半部分(mini∈TEi)
有一个naive的做法是列方程解,但复杂度为O(n32n),无法接受
考虑用树上消元
可以认定fi和ffai有关系,这里记fi=Ai×ffai+Bi,于是得到:
fi=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧Bi,rootAi×ffai+Bi,leaf1+degi1(ffai+k∈soni∑(Ak×fi+Bk)),other
化简得到
Ai=degi−∑k∈soniAk1,Bi=degi−∑k∈soniAk∑k∈soniBk+degi
于是一遍树形dp即可解出A,B,同时froot=Broot,复杂度变为O(n2n)
回到原问题:
i∈SmaxEi=T∈S∑(−1)∣T∣−1×i∈TminEi
把(−1)∣T∣−1加到fT中
i∈SmaxEi=T∈S∑fT
用SOS DP
或FWT
等等实现均可
code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
| #include<bits/stdc++.h> using namespace std; const int mxn=20; typedef long long ll; const ll p=998244353; int count(int x); ll qpow(ll a,ll b); void SOSpre();
int n,q,x; struct edg{ int v,next; }edge[mxn<<1]; int head[mxn<<1],cnt; void addedge(int u,int v) { edge[++cnt]=edg{v,head[u]}; head[u]=cnt; edge[++cnt]=edg{u,head[v]}; head[v]=cnt; } ll f[1<<mxn],A[mxn],B[mxn]; ll g[1<<mxn]; int U;
void dfs(int u,int fa,int S) { if(S>>(u-1)&1) return; ll inv=0,suma=0,sumb=0,deg=0; for(int i=head[u];i;i=edge[i].next) { int to=edge[i].v; deg++; if(to==fa) continue; dfs(to,u,S); suma+=A[to]; sumb+=B[to]; } inv=qpow(deg-suma,p-2)%p; A[u]=inv; B[u]=(sumb+deg)%p*inv%p; }
int main() { scanf("%d%d%d",&n,&q,&x); U=(1<<n); for(int i=1,a1,a2;i<n;i++) { scanf("%d%d",&a1,&a2); addedge(a1,a2); } for(int s=1;s<U;s++) { memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); dfs(x,0,s); if(count(s)%2==0) B[x]=(-B[x]%p+p)%p; f[s]=B[x]; } SOSpre(); while(q--) { int k,a1,ans=0; scanf("%d",&k); for(int i=1;i<=k;i++) { scanf("%d",&a1); ans=ans|(1<<(a1-1)); } printf("%lld\n",g[ans]%p); } }
void SOSpre() { for(int i=0;i<U;i++) g[i]=f[i]; for(int i=0;i<n;i++) { for(int j=0;j<U;j++) { if(j>>i&1) { g[j]+=g[j^(1<<i)]; g[j]=(g[j]%p+p)%p; } } } }
ll qpow(ll a,ll b) { ll ans=1,base=a; while(b>0) { if(b&1) ans=ans*base%p; base=base*base%p; b>>=1; } return ans; }
int count(int x) { int ans=0; for(int i=0;i<n;i++) ans=ans+(x>>i&1); return ans; }
|