LOJ #2542 [PKUWC2018]随机游走 (概率期望、组合数学、子集和变换、Min-Max容斥)

很好很有趣很神仙的题！

题意: 请自行阅读

题解首先我们显然要求的是几个随机变量的最大值的期望（不是期望的最大值），然后这玩意很难求，根据Min-Max容斥化成最小值的期望来求。

Minn-max容斥是指$\max(x_1,x_2,...,x_n)=\sum_{S\in \{1,2,...,n\} } (-1)^{|S|-1} \min_{i\in S}(x_i)$ (所有元素都是正整数，这个尽管式子本身和期望没关系但是经常是求期望的时候用它)

这个式子可以如此理解: 若把每个正整数$x$看作集合${1,2,...,x}$的话，则$\max$就是集合并，$\min$就是集合交，容斥原理直接推论

所以我们$O(2^n)$枚举每个关键点的子集，然后问题转化为: 按照同样的规则随机游走，走到任何一个关键点时即停，问期望步数

然后可以设$dp[x]$表示$x$节点作为起始点的期望步数

若$x$是关键点，$dp[x]=0$, 否则$dp[x]=\frac{1}{du[x]}\sum_{Edge(u,v)}{dp[v]}+1$ ($du[]$是度数)

然后我们就可以愉快地来个高斯消元$O(2^nn^3)$处理单个询问了。（能得多少分别问我，没试过……）

神仙之处在下面: $O(n)$求解树上高消

由于这是棵树，所以我们如果dfs的话，可以把$dp[x]$记成一个关于$dp[fa]$ ($fa$是父亲)的一次函数，形如$dp[x]=A_xdp[fa]+B_x$.

然后假设现在做到点$u$(非根)则$$dp[u]=\frac{dp[fa]+\sum_{v\in son(u)}{A_vdp[u]+B_v}}{du[u]}+1$$

\[(1-\frac{\sum_{v\in son(u)}{a_v}}{du[u]})dp[u]=\frac{dp[fa]}{du[u]}+(\frac{\sum_{v\in son(u)}B_v}{du[u]}+1)
\]

归纳易证，只要有特殊点($A=B=0$)的存在，等式左边$dp[u]$的系数恒大于$0$, 因此除过去就完成了$A$和$B$的递推！

裸做时间复杂度$O(2^nnq)$, 子集和变换（高维前缀和，又称FMT）可以做到$O(2^nn)$预处理$O(1)$查询

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<utility>

#define llong long long

using namespace std;

const int N = 18;

const int P = 998244353;

llong fact[(1<<N)+3],finv[(1<<N)+3];

struct Edge

{

	int v,nxt;

} e[(N<<1)+3];

int cnt[(1<<N)+3];

llong f[(1<<N)+3];

int fe[N+3];

int fa[N+3];

int du[N+3];

int n,q,s,en;

llong quickpow(llong x,llong y)

{

	llong cur = x,ret = 1ll;

	for(int i=0; y; i++)

	{

		if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}

		cur = cur*cur%P;

	}

	return ret;

}

llong mulinv(llong x) {return quickpow(x,P-2);}

void addedge(int u,int v)

{

	du[u]++;

	en++; e[en].v = v;

	e[en].nxt = fe[u]; fe[u] = en;

}

void dfs0(int u)

{

	for(int i=fe[u]; i; i=e[i].nxt)

	{

		if(e[i].v==fa[u]) continue;

		fa[e[i].v] = u;

		dfs0(e[i].v);

	}

}

pair<llong,llong> dfs(int u,int sta)

{

//	printf("dfs(%d)\n",u);

	if(sta&(1<<u)) {return make_pair(0,0);}

	pair<llong,llong> ret = make_pair(1,1);

	if(u!=s && du[u]==1) return ret;

	llong s1 = 0ll,s2 = 0ll;

	for(int i=fe[u]; i; i=e[i].nxt)

	{

		if(e[i].v==fa[u]) continue;

		pair<llong,llong> tmp = dfs(e[i].v,sta);

		s1 = (s1+tmp.first)%P,s2 = (s2+tmp.second)%P;

	}

	ret.first = mulinv(du[u]-s1+P)%P; ret.second = ret.first*(s2+du[u])%P;

	return ret;

}

int main()

{

	cnt[0] = 0; for(int i=1; i<(1<<N); i++) cnt[i] = cnt[i>>1]+(i&1);

	scanf("%d%d%d",&n,&q,&s); s--;

	for(int i=1; i<n; i++)

	{

		int x,y; scanf("%d%d",&x,&y); x--; y--;

		addedge(x,y); addedge(y,x);

	}

	fa[s] = -1; dfs0(s);

	for(int i=1; i<(1<<n); i++)

	{

		if(i&(1<<s)) {f[i] = 0ll; continue;}

		pair<llong,llong> tmp = dfs(s,i);

		f[i] = tmp.second;

		if((cnt[i]&1)==0) {f[i] = P-f[i];}

	}

	for(int i=0; i<n; i++)

	{

		for(int j=0; j<(1<<n); j++)

		{

			if(j&(1<<i)) {f[j] = (f[j]+f[j^(1<<i)])%P;}

		}

	}

	for(int i=1; i<=q; i++)

	{

		int n0; scanf("%d",&n0);

		int u = 0; for(int j=1; j<=n0; j++) {int x; scanf("%d",&x); x--; u+=(1<<x);}

		printf("%lld\n",f[u]);

	}

	return 0;

}