LOJ2542. 「PKUWC2018」随机游走

https://loj.ac/problem/2542

分析:

• 为了学习最值反演而做的这道题~
• • \(max{S}=\sum\limits_{T\subseteq S}(-1)^{|T|-1}min{T}\)
    
    考虑排序后的\(a\)序列。
• \(\sum\limits_{T\subseteq S}(-1)^{|T|-1}min{T}=\sum\limits_{i=1}^na_i\sum\limits_{j=0}^{n-i}(-1)^j\binom{n-i}{j}\)
• \(\sum\limits_{T\subseteq S}(-1)^{|T|-1}min{T}=\sum\limits_{i=1}^na_i[n-i=0]\)
• \(\sum\limits_{T\subseteq S}(-1)^{|T|-1}min{T}=a_n=max{S}\)
• 设\(f_{s,i}\)表示\(f\)第一次走到\(s\)状态的期望步数。
• 这个东西我们直接枚举\(s\)然后树上高斯消元即可。
• 最后再\(fwt\)一下就能得到反演后的\(min_s\)了。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <cmath>

using namespace std;

#define mod 998244353

typedef long long ll;

#define N 20

#define M ((1<<18)+50)

int n,head[N],to[N<<1],nxt[N<<1],du[N],rt,m;

int S,Cnt[M],cnt;

inline void add(int u,int v) {to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;}

ll K[N],B[N],inv[N],f[M];

ll qp(ll x,ll y) {

	ll re=1;

	for(;y;y>>=1,x=x*x%mod)if(y&1)re=re*x%mod;return re;

}

void dfs(int x,int y) {

	int i;

	if(S&(1<<(x-1))) {K[x]=B[x]=0; return ;}

	K[x]=inv[du[x]]; B[x]=1; ll lhs=1;

	for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {

		dfs(to[i],x);

		lhs=(lhs-K[to[i]]*inv[du[x]])%mod;

		B[x]=(B[x]+B[to[i]]*inv[du[x]])%mod;

	}

	lhs=qp(lhs,mod-2);

	K[x]=K[x]*lhs%mod; B[x]=B[x]*lhs%mod;

}

void fwt(ll *a,int len) {

	int i,j,k,t;

	for(k=2;k<=len;k<<=1) for(t=k>>1,i=0;i<len;i+=k) for(j=i;j<i+t;j++) a[j+t]=(a[j+t]+a[j])%mod;

}

int main() {

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

	int i,x,y;

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

		scanf("%d%d",&x,&y); add(x,y); add(y,x); du[x]++; du[y]++;

	}

	for(i=1;i<=n;i++) inv[i]=qp(i,mod-2);

	int mask=(1<<n)-1;

	for(i=0;i<=mask;i++) {

		S=i;

		dfs(rt,0);

		Cnt[i]=Cnt[i>>1]+(i&1);

		f[i]=B[rt];

		if(!(Cnt[i]&1)) f[i]=-f[i];

	}

	fwt(f,(1<<n));

	while(m--) {

		int k,s=0;

		scanf("%d",&k);

		while(k--) {

			scanf("%d",&x); s|=(1<<(x-1));

		}

		printf("%lld\n",(f[s]+mod)%mod);

	}

}