LOJ2542. 「PKUWC2018」随机游走

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);
}
}
上一篇:【理论】X理论、Y理论及Z理论


下一篇:loj#2542. 「PKUWC2018」随机游走(树形dp+Min-Max容斥)