Liveddd's Blog

愛にできることはまだあるかい

LOJ#2542. 「PKUWC2018」随机游走

发表于 更新于 分类于
本文字数： 3.6k 阅读时长 ≈ 8 分钟

min-max 容斥 练手题。

发现要求的是：

使用 min-max 容斥得到：

注意到 $n\le 18$，于是考虑直接暴力容斥，求出每个子集 $S$ 的 $\displaystyle E(\min_{i\in S} t_i) $。

设计状态 $f(i)$ 表示从 $i$ 走到第一次走到 $S$ 中任意点的期望步数，

1.对于 $i\in S$，有 $f(i)=0$。

2.对于 $i\notin S$，有 $\displaystyle f(i)=1+\frac{1}{\deg(i)}\sum_{(i,j)\in E} f(j)$。

可以高斯消元，但是时间复杂度就变成 $\mathcal O(n^3 2^n)$ 的，不能接受。

先考虑叶子节点 $i$，它们的值只会与父亲有关（或者 $f(i)=0$），有 $f(i)=A_i f(p_i) +B_i$，其中 $A_i=1,B_i=1$。而我们接着考虑叶子的父亲节点 $i$：

变换一下：

于是我们将叶子的父亲节点 $i$ 也表示成了类似于 $\displaystyle f(i)=A_i f(p_i) +B_i$ 的形式，其中 $\displaystyle A_i=\frac{1}{\deg(i)-\sum_j{A_j}},B_i=\frac{\deg(i)+\sum_j B_j}{\deg(i)-\sum_j A_j}$。

以此类推，我们从下往上可以推出所有节点的 $A_i,B_i$，我们直接以 $x$ 为根，因为 $x$ 没有父节点，所以：

于是对与每个 $S$ dfs 一遍即可求出对应的 $f(x)$，时间复杂度为 $\mathcal O(n2^n)$。

但是我们要求的是 $\displaystyle \sum_{T\subseteq S}(-1)^{|T|-1} E(\min_{i\in T} t_i)$，对于每个询问求一次是 $\mathcal O(2^n)$ 的。对于这个式子，我们显然可以在预处理出所有 $\displaystyle (-1)^{|T|-1} E(\min_{i\in T} t_i)$ 后，做一次 FMT，即可 $\mathcal O(1)$ 回答询问。

代码非常好写。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<iostream>
#include<cstdio>
#define popcnt __builtin_popcount
using namespace std;
const int N=18,mod=998244353;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,q,rt;
int tot,head[N],ver[N<<1],ne[N<<1];
int s,deg[N],a[N],b[N];
int f[1<<N];
inline int adj(int x){return (x>=mod)?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}

void dfs(int x,int fa)
{
    if(s>>x&1)
    {
        a[x]=0,b[x]=0;
        return ;
    }
    int suma=0,sumb=0;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        suma=adj(suma+a[y]),sumb=adj(sumb+b[y]);
    }
    a[x]=qpow(adj(deg[x]-suma+mod));
    b[x]=1ll*adj(deg[x]+sumb)*qpow(adj(deg[x]-suma+mod))%mod;
}
inline void FMT(int n,int *a)
{
    int tot=1<<n;
    for(int i=0;i<n;i++)
        for(int j=0;j<tot;j++)
            if(j>>i&1)
                a[j]=adj(a[j]+a[j^(1<<i)]);
}
int main()
{
    read(n,q,rt);
    rt--;
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u,v);
        u--,v--;
        add(u,v),add(v,u);
        deg[u]++,deg[v]++;
    }
    for(s=1;s<(1<<n);s++)
    {
        int op=(popcnt(s)&1)?1:-1;
        dfs(rt,-1);
        f[s]=adj(op*b[rt]+mod);
    }
    FMT(n,f);
    while(q--)
    {
        int k;
        read(k);
        s=0;
        for(int i=0;i<k;i++)
        {
            int x;
            read(x);
            x--;
            s+=1<<x;
        }
        printf("%d\n",f[s]);
    }
    return 0;
}