「PKUWC2018」随机游走（min-max容斥+FWT）

以后题目都换成这种「」形式啦，我觉得好看。

做过重返现世的应该看到就想到 \(min-max\) 容斥了吧。

没错，我是先学扩展形式再学特殊形式的。

问题转化之后，然后我们可以枚举所有状态然后 \(O(n)\) 树形 \(dp\)

\(-1\) 那项可以 \(O(2^n)\) 推出来，接下来就是子集变换了。可以 \(O(n2^n)\) \(FWT\) 或者 \(O(3^n)\) 暴力枚举，自己喜欢哪种就上吧。

\(Code\ Below:\)

#include <bits/stdc++.h>

using namespace std;

const int mod=998244353;

int n,q,rt,lim,bin[20],a[20],b[20],d[20],f[1<<18],g[1<<18];

vector<int> G[20];

inline int fpow(int a,int b){

	int ret=1;

	for(;b;b>>=1,a=1ll*a*a%mod)

		if(b&1) ret=1ll*ret*a%mod;

	return ret;

}

void dfs(int x,int f,int S){

	if(S&bin[x]) return ;

	a[x]=d[x];b[x]=1;

	int tmp=1,y;

	vector<int>::iterator it;

	for(it=G[x].begin();it!=G[x].end();it++){

		y=*it;

		if(y==f) continue;

		dfs(y,x,S);

		tmp=(tmp-1ll*a[y]*d[x]%mod+mod)%mod;

		b[x]=(b[x]+1ll*b[y]*d[x]%mod)%mod;

	}

	tmp=fpow(tmp,mod-2);

	a[x]=1ll*a[x]*tmp%mod;

	b[x]=1ll*b[x]*tmp%mod;

}

inline void FWT(){

	for(int len=1;len<lim;len<<=1)

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

			if(i&len) f[i]=(f[i]+f[i^len])%mod;

}

int main()

{

	scanf("%d%d%d",&n,&q,&rt);

	rt--;lim=1<<n;bin[0]=1;

	for(int i=1;i<=n;i++) bin[i]=bin[i-1]<<1;

	int x,y,k,S;

	for(int i=0;i<n-1;i++){

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

		x--;y--;

		G[x].push_back(y);

		G[y].push_back(x);

		d[x]++;d[y]++;

	}

	for(int i=0;i<n;i++) d[i]=fpow(d[i],mod-2);

	for(int i=0;i<lim;i++){

		for(int j=0;j<n;j++) a[j]=b[j]=0;

		dfs(rt,-1,i);f[i]=b[rt];

	}

	g[0]=-1;

	for(int i=1;i<lim;i++) g[i]=g[i>>1]*((i&1)?-1:1);

	for(int i=0;i<lim;i++){

		f[i]*=g[i];

		if(f[i]<0) f[i]+=mod;

	}

	FWT();

	while(q--){

		scanf("%d",&k);S=0;

		for(int i=1;i<=k;i++){

			scanf("%d",&x);

			S|=bin[x-1];

		}

		printf("%d\n",f[S]);

	}

	return 0;

}