CF1236F - Alice and the Cactus

Posted on Edited on In

CF1236F - Alice and the Cactus

题目大意

给定一棵仙人掌，现在每个点有 \(\frac{1}{2}\) 概率被删除

设删除后剩余连通块数为 \(\Chi\) ，求 \(D(\Chi)\) （ \(D\) 为方差）


分析

由简单结论 \(D(\Chi)=E(\Chi^2)-E^2(\Chi)\)

考虑计算 \(E(\Chi ^2),E(\Chi)\) ，也就是计算所有情况下 \(\Chi^2,\Chi\) 之和

实际上对于计算 \(E(\Chi^k)\) 的情况，可以记录 \(E(\Chi^i),i\in[0,k]\) 所有的答案

然后在仙人掌上 \(dp\) ，每次合并两个 \(dp\) 时对于 \((\Chi+\Chi')^i\) 做二项展开计算答案

环上 \(dp\) 记录开头和结尾的一些状态即可

如果分裂出一个连通块，就对于当前 \(\Chi^i\rightarrow (\Chi+1)^i\) ，同样是二项展开

具体不再赘述

复杂度为 \(O(n)\)

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
const int N=5e5+10,P=1e9+7;

int n,m;
struct Node{
    int x,y,z;
    Node(){}
    Node(int x,int y,int z):x(x),y(y),z(z){}
    Node operator * (const Node t) const {
        return Node(1ll*x*t.x%P,
                (1ll*y*t.x+1ll*t.y*x)%P,
                (1ll*z*t.x+1ll*t.z*x+2ll*y*t.y)%P);
    }
    Node operator + (const Node t) const { 
        return Node((x+t.x)%P,(y+t.y)%P,(z+t.z)%P);
    }
    Node operator + (const int t) const { 
        return Node(x,(y+1ll*t*x)%P,(z+2ll*y*t+1ll*x*t%P*t%P)%P);
    }
    Node operator * (const int t) const {
        return Node(1ll*x*t%P,1ll*y*t%P,1ll*z*t%P);
    }
} dp[N][2],f[N][2][3];

struct Edge{
    int to,nxt;
} e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v) {
    e[++ecnt]=(Edge){v,head[u]};
    head[u]=ecnt;
}

int low[N],t[N],dfn,stk[N],top;
int A[N],C;
void dfs(int u) {
    low[u]=t[u]=++dfn,stk[++top]=u;
    dp[u][0]=Node(1,0,0),dp[u][1]=Node(1,0,0);
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if(t[v]) {
            cmin(low[u],t[v]);
            continue;
        }
        dfs(v),cmin(low[u],low[v]);
        if(low[v]<t[u]) continue;
        A[C=1]=u;
        while(t[stk[top]]>=t[v]) A[++C]=stk[top--];
        rep(i,1,C) rep(a,0,1) rep(b,0,2) f[i][a][b]=Node(0,0,0);
        f[1][0][0]=dp[u][0], f[1][1][2]=dp[u][1];
        rep(i,2,C) {
            rep(a,0,1) rep(b,0,2) {
                rep(c,0,1) {
                    int d=c==1 && b==2?b:c;
                    f[i][a][d]=f[i][a][d]+(f[i-1][a][b]*dp[A[i]][c]+(b==1 && !c));
                }
            }
        }
        dp[u][0]=dp[u][1]=Node(0,0,0);
        rep(a,0,1) rep(b,0,2) {
            dp[u][a]=dp[u][a]+(f[C][a][b]+(b==1 && !a));
        }
    }
}

int main(){
    n=rd(),m=rd();
    rep(i,1,m) {
        int u=rd(),v=rd();
        AddEdge(u,v),AddEdge(v,u);
    }
    dfs(1);
    int base=1;
    rep(i,1,n) base=1ll*base*(P+1)/2%P;
    Node ans=dp[1][0]+(dp[1][1]+1);
    ans=ans*base;
    int D=((ans.z-1ll*ans.y*ans.y)%P+P)%P;
    printf("%d\n",D);
}