【LOJ#2542】[PKUWC2018]随机游走（min-max容斥，动态规划）

时间：2022-01-08 18:25:16

【LOJ#2542】[PKUWC2018]随机游走（min-max容斥，动态规划）

题面

LOJ

题解

很明显，要求的东西可以很容易的进行\(min-max\)容斥，那么转为求集合的\(min\)。

那么怎么求解每个集合的\(min\)呢。

显然以起点为根节点，如果点集中一个点在另外一个点的子树内，显然不需要考虑，索性丢掉。考虑剩下的点，把他们的子树丢掉（要访问子树肯定要访问到某个点），那么剩下的点直接扣下来做一个高斯消元就可以求出到达每个点的期望，那么\(min\)就求出来。

设\(f[S]\)表示点集\(S\)在以\(x\)为根的时候的\(min\)。这个东西直接预处理的话，复杂度是\(O(2^n n^3)\)，

然而我们并不需要裸的高斯消元，树上的高斯消元是可以做到\(O(n)\)的。大概就是叶子节点可以表示成只含有父亲的一个一次函数，把这个东西带到其父亲的方程中消去这个叶子节点，这样子就少了一个元，可以做到线性。

啥？方程不会列？设\(f[i]\)表示从当前点\(i\)到达一个最近的点集中的点的期望。$\displaystyle f[u]=1+\frac{1}{d}\sum_{v,(u,v)\in E}f[v] $。然后点集中的点特殊处理一下。

然后就没了

#include<iostream>

#include<cstdio>

using namespace std;

#define MOD 998244353

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int fpow(int a,int b)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

struct Line{int v,next;}e[40];

int h[20],cnt=1,dg[20];

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;++dg[u];}

int n,Q,r,All,a[1<<18],bul[1<<18];

int k[20],b[20];

void dfs(int u,int ff,int S)

{

	if(S&(1<<u)){k[u]=b[u]=0;return;}

	int sk=0,sb=0;

	for(int i=h[u];i;i=e[i].next)

		if(e[i].v!=ff)

			dfs(e[i].v,u,S),sk=(sk+k[e[i].v])%MOD,sb=(sb+b[e[i].v])%MOD;

	k[u]=fpow((dg[u]-sk+MOD)%MOD,MOD-2);

	b[u]=1ll*k[u]*(sb+dg[u])%MOD;

}

int main()

{

	n=read();Q=read();r=read()-1;All=(1<<n)-1;

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

	{

		int u=read()-1,v=read()-1;

		Add(u,v);Add(v,u);

	}

	for(int i=1;i<=All;++i)bul[i]=bul[i>>1]+(i&1);

	for(int i=1;i<=All;++i)dfs(r,-1,i),a[i]=b[r];

	for(int i=1;i<=All;++i)if(!(bul[i]&1))a[i]=(MOD-a[i])%MOD;

	for(int i=1;i<=All;i<<=1)

		for(int p=i<<1,j=0;j<=All;j+=p)

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

				a[i+j+k]=(a[i+j+k]+a[j+k])%MOD;

	while(Q--)

	{

		int S=0,t=read();

		while(t--)S|=1<<(read()-1);

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

	}

	return 0;

}

相关文章