LOJ2542 PKUWC2018 随机游走 min-max容斥、树上高斯消元、高维前缀和、期望

传送门

---

那么除了D1T3，PKUWC2018就更完了（斗地主这种全场0分的题怎么会做啊）

发现我们要求的是所有点中到达时间的最大值的期望，(n)又很小，考虑min-max容斥

那么我们要求从(x)走到第一个属于某个子集(S)的节点的步数期望，这是一个经典的树上高斯消元问题。

将树设为以(x)为根，设(f_{i , S})为从第(i)个点随机游走到达点集(S)任意一个点停止，行走步数的期望，转移：

(1.i in S: f_{i , S}=0)

(2.i otin S : f_{i , S} = frac{1}{in_i} sumlimits_{(i,j) in e}f_{j,S} + 1)

直接这么做是(O(2^nn^3))的，但是因为树上的优美性质，高斯消元可以做到(O(n))。

首先对于一个点集(S)中的点(t)，(t)的子树是没有必要的，可以截去。

然后对于所有叶子节点(k)，要么(f_{k , S} = 0) ，要么(f_{k , S} = f_{fa_k , S} + 1)。可以发现对于当前的某一个点(x)，如果它的所有子节点(y)都是叶子节点，可以通过消元将(f_{x,S})变为(k imes f_{fa_k , S} + b)的形式，其中(k,b)都是常数。这么按照无根树拓扑序推上去，可以知道除根结点的所有节点(x)，(f_{x , S} = k imes f_{fa_x , S} + b)的形式，而根结点可以推出(f_{x,S} = b)，就可以求出来从根结点走到第一个属于(S)的节点的步数期望了。

乘上(-1^{|S| + 1})之后，题目求的最大值期望实质上就是一个子集和，高维前缀和之后(O(1))回答询问，总复杂度(O(n2^n + Q))。

#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;

inline int read(){
	int a = 0;
	char c = getchar();
	bool f = 0;
	while(!isdigit(c) && c != EOF){
		if(c == '-')
			f = 1;
		c = getchar();
	}
	if(c == EOF)
		exit(0);
	while(isdigit(c)){
		a = a * 10 + c - 48;
		c = getchar();
	}
	return f ? -a : a;
}

const int MOD = 998244353;
struct Edge{
	int end , upEd;
}Ed[41];
int head[21] , dp[1 << 18] , du[21] , k[21] , b[21] , cnt1[1 << 18];
int N , Q , R , cntEd;

inline int poww(long long a , int b){
	int times = 1;
	while(b){
		if(b & 1)
			times = times * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return times;
}

inline void addEd(int a , int b){
	Ed[++cntEd].end = b;
	Ed[cntEd].upEd = head[a];
	head[a] = cntEd;
	++du[b];
}

void dfs(int x , int p , int S){
	if(S & (1 << x)){
		k[x] = b[x] = 0;
		return;
	}
	k[x] = 1;
	b[x] = 0;
	int t = poww(du[x] , MOD - 2);
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p){
			dfs(Ed[i].end , x , S);
			k[x] = (k[x] - 1ll * k[Ed[i].end] * t % MOD + MOD) % MOD;
			b[x] = (b[x] + 1ll * t * b[Ed[i].end]) % MOD;
		}
	k[x] = poww(k[x] , MOD - 2);
	b[x] = 1ll * (b[x] + 1) * k[x] % MOD;
	k[x] = 1ll * k[x] * t % MOD;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	N = read();
	Q = read();
	R = read() - 1;
	for(int i = 1 ; i < N ; ++i){
		int a = read() - 1 , b = read() - 1;
		addEd(a , b);
		addEd(b , a);
	}
	for(int i = 1 ; i < 1 << N ; ++i){
		dfs(R , -1 , i);
		dp[i] = b[R];
	}
	for(int i = 1 ; i < 1 << N ; ++i){
		cnt1[i] = cnt1[i >> 1] + (i & 1);
		if(!(cnt1[i] & 1))
			dp[i] = dp[i] ? MOD - dp[i] : 0;
	}
	for(int i = 0 ; i < N ; ++i)
		for(int j = 1 ; j < 1 << N ; ++j)
			if(!(j & (1 << i)))
				(dp[j | (1 << i)] += dp[j]) %= MOD;
	for(int i = 1 ; i <= Q ; ++i){
		int S = 0;
		for(int j = read() ; j ; --j)
			S += 1 << (read() - 1);
		printf("%d
" , dp[S]);
	}
	return 0;
}