高质量免费的网站,tv做后缀的动漫网站,深圳网页制作推广排名,红酒网站模板正题
题目链接:https://www.luogu.com.cn/problem/P5643 题目大意
给出nnn个点的一棵树#xff0c;一个人从点xxx开始随机游走#xff0c;然后QQQ次询问给出一个点集SSS#xff0c;求期望多少步这个人会经过这个点集中的所有点。 1≤n≤18,1≤Q≤50001\leq n\leq 18,1\leq…正题
题目链接:https://www.luogu.com.cn/problem/P5643 题目大意
给出nnn个点的一棵树一个人从点xxx开始随机游走然后QQQ次询问给出一个点集SSS求期望多少步这个人会经过这个点集中的所有点。
1≤n≤18,1≤Q≤50001\leq n\leq 18,1\leq Q\leq 50001≤n≤18,1≤Q≤5000 解题思路
整个点集都走完比较难统计我们可以考虑用min−maxmin-maxmin−max容斥转为求走到其中一个点的期望步数。
我们设我们目前枚举的集合是SSS那么首先有fx0(x∈S)f_x0(x\in S)fx0(x∈S)
然后有转移方程 fx1degx(ffax∑x→yfy)f_{x}\frac{1}{deg_x}(f_{fa_x}\sum_{x\rightarrow y}f_{y})fxdegx1(ffaxx→y∑fy) 惯例的我们设fxAxffaxBxf_xA_xf_{fa_x}B_xfxAxffaxBx fx1degx(ffax∑x→y(AyfxBy))f_{x}\frac{1}{deg_x}\left(f_{fa_x}\sum_{x\rightarrow y}(A_yf_xB_y)\right)fxdegx1(ffaxx→y∑(AyfxBy)) fx1degxffaxsumAfxdeg1degxsumB1f_{x}\frac{1}{deg_x}f_{fa_x}\frac{sumAf_x}{deg}\frac{1}{deg_x}sumB1fxdegx1ffaxdegsumAfxdegx1sumB1 degx−sumAdegxfx1degxffax1degxsumB1\frac{deg_x-sumA}{deg_x}f_x\frac{1}{deg_x}f_{fa_x}\frac{1}{deg_x}sumB1degxdegx−sumAfxdegx1ffaxdegx1sumB1 fx1degx−sumAffaxdegxsumBdegx−sumAf_x\frac{1}{deg_x-sumA}f_{fa_x}\frac{deg_xsumB}{deg_x-sum_A}fxdegx−sumA1ffaxdegx−sumAdegxsumB
这样我们就可以推出AAA和BBB而BxB_xBx就是节点xxx的fff值记gSBxg_SB_xgSBx。
那么根据min-max容斥如果我们询问集合SSS时答案就是 ∑T⊆S(−1)∣T∣1gT\sum_{T\sube S}(-1)^{|T|1}g_TT⊆S∑(−1)∣T∣1gT
用个高维前缀和就可以预处理所有集合的答案了。
时间复杂度O(n2nlogP)O(n2^n\log P)O(n2nlogP) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N18,P998244353;
struct node{ll to,next;
}a[N1];
ll n,Q,rt,tot,ls[N],deg[N];
ll A[N],B[N],c[1N],f[1N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;deg[y];return;
}
void dfs(ll x,ll fa,ll S){ll sumA0,sumB0;if((Sx)1){A[x]B[x]0;return;}for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x,S);sumA(sumAA[y])%P;sumB(sumBB[y])%P;}ll invpower((deg[x]-sumAP)%P,P-2);A[x]inv;B[x](deg[x]sumB)*inv%P;return;
}
signed main()
{scanf(%lld%lld%lld,n,Q,rt);rt--;for(ll i1,x,y;in;i){scanf(%lld%lld,x,y);x--;y--;addl(x,y);addl(y,x);}ll MS(1n);for(ll s1;sMS;s){memset(A,0,sizeof(A));memset(B,0,sizeof(B));dfs(rt,n,s);f[s]B[rt];}for(ll s1;sMS;s){c[s]c[s-(s-s)]1;f[s]((c[s]1)?f[s]:(P-f[s]));}for(ll i0;in;i)for(ll sMS-1;s0;s--)if((si)1)(f[s]f[s-(1i)])%P;while(Q--){ll k,s0;scanf(%lld,k);for(ll i0,x;ik;i)scanf(%lld,x),s|(1x-1);printf(%lld\n,f[s]);}return 0;
}
