vue2.0网站开发,公司招聘网站排行榜,建设设计公司网站,建设网站费用如何做账题意#xff1a;给一棵nnn个点的无权树和xxx#xff0c;qqq次询问#xff0c;每次给定一个点集SSS,询问从xxx开始每次随机走一步#xff0c;SSS中的每个点至少被经过一次的期望步数。 n≤18,q≤5000n\leq 18,q\leq 5000n≤18,q≤5000
题目求的相当于是SSS中的所有点 第一次…题意给一棵nnn个点的无权树和xxxqqq次询问每次给定一个点集SSS,询问从xxx开始每次随机走一步SSS中的每个点至少被经过一次的期望步数。
n≤18,q≤5000n\leq 18,q\leq 5000n≤18,q≤5000
题目求的相当于是SSS中的所有点 第一次被访问的时间 的最大值 的期望发现nnn很小可以Min-Max容斥成第一次到SSS 中任意一个点的期望时间。
然后考虑 dp。设xxx为根fuf_ufu表示从uuu开始到SSS中任意一个点的期望时间。
fu1degu(ffau∑v∈sonufv)1f_u\frac{1}{deg_u}(f_{fa_u}\sum _{v\in son_u}f_v)1fudegu1(ffauv∈sonu∑fv)1
degu⋅fuffau∑v∈sonufvdegudeg_u\cdot f_uf_{fa_u}\sum _{v\in son_u}f_vdeg_udegu⋅fuffauv∈sonu∑fvdegu
一个套路待定系数法设fukuffaubuf_uk_uf_{fa_u}b_ufukuffaubu
degu⋅fuffau∑v∈sonu(kvfubv)degudeg_u\cdot f_uf_{fa_u}\sum _{v\in son_u}(k_vf_ub_v)deg_udegu⋅fuffauv∈sonu∑(kvfubv)degu
(degu−∑kv1)⋅fuffau∑bvdegu(deg_u-\sum k_v1)\cdot f_uf_{fa_u}\sum b_vdeg_u(degu−∑kv1)⋅fuffau∑bvdegu
解得
kv1degu−∑kv1k_v\frac{1}{deg_u-\sum k_v1}kvdegu−∑kv11
bv∑bvdegudegu−∑kv1b_v\frac{\sum b_vdeg_u}{deg_u-\sum k_v1}bvdegu−∑kv1∑bvdegu
如果u∈Su\in Su∈S有fu0f_u0fu0对它的父亲没有贡献直接kubu0k_ub_u0kubu0
SSS的答案就是fxbxf_xb_xfxbx乘上容斥系数再FWT一下就可以快速回答询问
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
using namespace std;
const int MOD998244353;
typedef long long ll;
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD,p1;}return ans;
}
#define inv(x) qpow(x,MOD-2)
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
int k[20],b[20];
vectorint e[20];
void dfs(int u,int f,int S)
{if (S(1u)) return (void)(k[u]b[u]0);int sumk0,sumb0;for (int i0;i(int)e[u].size();i)if (e[u][i]!f)dfs(e[u][i],u,S),sumkadd(sumk,k[e[u][i]]),sumbadd(sumb,b[e[u][i]]);k[u]inv(dec((int)e[u].size(),sumk)),b[u]((ll)e[u].size()sumb)*k[u]%MOD;
}
int f[120];
int main()
{int n,q,x;scanf(%d%d%d,n,q,x);for (int i1;in;i){int u,v;scanf(%d%d,u,v);e[u].push_back(v),e[v].push_back(u);}for (int S1;S(1n);S){dfs(x,0,S1);f[S]b[x];int c0;for (int i0;in;i) c^(Si)1;if (!c) f[S]dec(0,f[S]);}for (int l0;ln;l){int mid1l,lenmid1;for (int s0;s(1n);slen)for (int k0;kmid;k)f[smidk]add(f[smidk],f[sk]);}while (q--){int S0;int k;scanf(%d,k);for (int i1;ik;i){int x;scanf(%d,x);S|1x;}printf(%d\n,f[S1]);}return 0;
}
