题解：P11834 [省选联考 2025] 岁月（补充题解）

xzf_200906 · 2025-03-05 11:30:53 · 题解

upd on 2025.03.08：修改了一处笔误并补充了一个内容。

此篇文章是对另一篇题解从性质 C 扩展到正解的“细枝末节的地方”的补充，下文将默认读者看过另一篇题解。

在看完那篇题解之后，如果读者已经知晓此题的解法，那么请退出此文章，因为这篇文章已经没用了。如果读者还不清楚性质 C 怎么做或者不知道如何判定一张图合法，那么请回去再仔细阅读。如果读者已经知晓上述内容，但不知道如何将性质 C 的解法套用到正解上（即那篇文章的倒数第二段不清楚），那么请往下看。

枚举边权，将所有边权相同的边的两端所在的连通块合并。注意，在不加说明的情况下，下面所称的连通块为合并之前的连通块。假设将 S_1,S_2,\cdots,S_k 合并成了一个，我们已经求出了原来的每个连通块中的每一个集合 s 成为该连通块的合法点集的概率 res_s，考虑如何通过它来求出新的 res。类比性质 C，s 合法当且仅当：

对于 s 中的每个元素，其在原来的连通块中合法。
若将每个连通块 S_i 看作一个点，将在不同的连通块之间且终点合法的边加入后，每个和 s 有交的连通块 S_i 均可以到达其它所有点。
按照条件 3 处理后，每个和 s 不交的连通块 S_i 均不完全能到达其它点。

下文将分部分讨论上述条件。

Part 2

大体和 C 性质的部分相同，但由于我们已知 s 中的所有点合法，那么对于任意的 u\in s，其可以到达其所在连通块的所有点。在 DP 的过程中我们会对缩点后有多个点的 DAG 进行计数。那么这张 DAG 一定满足以下条件：

由于在原来的连通块中的合法点集组成一个强连通分量，故对于 DAG 中的任意两个点，它们所代表的强连通分量所在的连通块不交。
对于其中的任意两个强连通分量 u,v，记 ext_u 表示和 u 中任意一个点在同一个连通块的点组成的集合，若不存在边 u\to v，则原图中不存在边 p\to q 满足 p\in ext_u,q\in v。

记 ok(s,t)=[ext_s\cap ext_t=\emptyset]，ans_s 为 s 在所有点在原来合法的前提下为强连通图的概率，则有如下转移方程：

ans_s=1-(g_s-ans_s)-\sum_{\emptyset \neq t\sub s}ok(s\setminus t,t) g_t2^{-cross(ext_{s\setminus t},t)}

g_s=ans_s-\sum_{lowbit(s)\in t\subseteq s}ok(s\setminus t,t)ans_tg_{s\setminus t}2^{-(cross(ext_{s\setminus t},t)+cross(ext_{t},s\setminus t))}

解释一下上面的式子，由于需要保证一个连通块不涉及到两个强连通分量，则需要计算 ok 函数。在计算 g_s 时需要在集合 s\setminus t 的基础上并上 t，且 t 和之前的所有点都没有边，则有 cross(ext_{s\setminus t},t)+cross(ext_{t},s\setminus t) 条边不能存在。而在计算 ans_s 的时候需要保证 s\setminus t 没有连向 t 的边，故有 cross(ext_{s\setminus t},t) 条边不能存在，故有以上转移系数。如果有其它部分不能看懂请看此题。

Part 4

最简单的一个，枚举所有和集合无交的连通块，统计起点在该连通块内，终点在 s 中的边的数量。在 s 中的所有点在原来合法的前提下，s 符合该条件当且仅当这些边不存在。设 cnt_s 为这些边的数量，则在该前提下 s 符合该条件的概率为 2^{-cnt_s}。

Part 1&3

类似于性质 C，先考虑一个较为暴力的算法。枚举一个集合 r 并分别计算其符合条件的概率。设 f_s 表示 s 中的点在原来全部为合法点且 r 可以到达所有与 s 有交的连通块的概率。

Q：为什么要这样设计状态而不是定义为直接从 r\to s 的概率？

A：因为 Part 3 中的点是原来的一整个连通块，如果 s 是指的原图中的点集，那么这样的状态是没意义的。如果 s 指的是可达的连通块组成的集合，那么由于要求每条边的终点在原来合法，这就意味着原来的合法点会影响转移系数，但是我们不可能在每次转移 f_t\to f_s 时都枚举哪些点合法（存疑，如果有人有思路的话请踢我），所以就这样设计状态了。

本质上 f_s 实际上记录了两个状态：哪些连通块可达和已经可达的连通块中有哪些点合法，但是由于从后面的信息可以推出前面的信息，所以就只要记录后面的东西。

由于一个连通块以前的合法点现在要么全不合法，要么全合法，故只有 r\subseteq s 且不存在一个连通块同时包含 r 和 s\setminus r 时 f_s 才有意义。则考虑枚举 t\sub s，计算 r 只能到达 t 的概率并从总概率中减去。设 cof_s 表示 s 中的点在之前全部为关键点的概率，则：

f_s=cof_s-\sum_{r\subseteq t\sub s}ok(t,s\setminus t)f_t2^{-cross(ext_t,s\setminus t)}cof_{s\setminus t}

由于我们已经确定了 t 中和其相交的每一个连通块中的合法点，不可以对其再作修改，所以仍然要计算 ok(t,s\setminus t)。

但是按上述转移方程暴力计算是不优的，联想到在 C 性质中的优化，上述 DP 本质上相当于建立一张边权为 -f_t2^{-cross(ext_t,s\setminus t)}cof_{s\setminus t} 的边，求每条起点为 p\supe r 且 ok(r,p\setminus r)=1，终点为全集的路径经过的边权之积乘上 cof_p 的和。考虑倒着跑 DP，求出每个点到全集的路径权值和，再乘上 cof_p，最后再计算 tf_s=\sum_{t\supe s} ok(s,t\setminus s) f_t 即可。

在计算完上述概率后，由于它们之间互相独立，则 res_s=ans_s\times 2^{-cnt_s}\times tf_s，最终的答案为 \sum res_s。

附一份加上了注释的部分上述题解的代码：

int fa[25],bel[2][25],_msk[25],ext[2][1 << 15],con[1 << 15];
//_msk: 连通块的点集
//bel: 上一时刻和这一时刻和该点同连通块的点
//ext: 两时刻该集合同连通块的点
//con：这一时刻集合内部是否为同一连通块
int fnd(int u){
    if(fa[u] == u) return u;
    return fa[u] = fnd(fa[u]);
}

int mrg(int u,int v){
    u = fnd(u);v = fnd(v);
    if(u == v) return 0;
    fa[u] = v;
    return 1;
}

void init(){
    rep(u,0,n - 1) _msk[u] = 0;
    rep(u,0,n - 1) _msk[fnd(u)] |= 1 << u;
    fill(con,con + (1 << n),0);
    rep(u,0,n - 1) bel[1][u] = _msk[fnd(u)];
    con[0] = 1;
    rep(u,0,n - 1){
        for(int S = _msk[u];S;S = (S - 1) & _msk[u]) con[S] = 1;
    }
    rep(S,1,(1 << n) - 1){
        int u = ctz(S);
        ext[1][S] = ext[1][S - (1 << u)] | bel[1][u];
    }
}

int cross(int S,int T){
    assert((S & T) == 0);
    return sum[S + T] - sum[S] - sum[T];
}

int ok(int S,int T){
    //上一时刻两集合所属块是否不交
    return (ext[0][S] & ext[0][T]) == 0;
}
Z f[1 << 15],g[1 << 15],tf[1 << 15];

Z ans[1 << 15],cof[1 << 15],dp[1 << 15];
Z res[1 << 15];
void solve(){
    scanf("%d%d",&n,&m);
    P[0] = 1;
    rep(i,1,n * n) P[i] = P[i - 1] * 2;
    rep(i,0,n * n) iP[i] = Z(1) / P[i];
    fill(msk,msk + n,0);
    rep(i,1,m){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
        E[i].u--;E[i].v--;
    }
    sort(E + 1,E + m + 1,cmp);
    rep(u,0,n - 1) fa[u] = u;
    init();
    rep(S,0,(1 << n) - 1) res[S] = 0;
    rep(i,0,n - 1) res[1 << i] = 1;
    for(int l = 1,r;l <= m;l = r + 1){
        r = l;
        while(r < m && E[r].w == E[r + 1].w) r++;
        rep(u,0,n - 1){
            swap(bel[0][u],bel[1][u]);
            msk[u] = 0;
        }
        rep(S,0,(1 << n) - 1) swap(ext[0][S],ext[1][S]);
        //保存上一时刻的连通性
        int succ = 0;
        rep(i,l,r){
            if(mrg(E[i].u,E[i].v)) succ = 1;
            msk[E[i].u] |= 1 << E[i].v;msk[E[i].v] |= 1 << E[i].u;
        }  
        init();
        //处理这一时刻的连通性
        if(!succ) continue;
        rep(S,1,(1 << n) - 1){
            int u = ctz(S);
            sum[S] = sum[S - (1 << u)] + popcnt(msk[u] & S);
        }
        //处理集合内的边，sum[S] 为两端均在 S 中的边的数量
        int stable = 0;
        rep(u,0,n - 1) if(bel[0][u] == bel[1][u]) stable |= 1 << u;
        rep(S,0,(1 << n) - 1) ans[S] = cof[S] = dp[S] = 0;
        cof[0] = -1;dp[0] = 1;
        //cof[0] 没有影响
        rep(S,1,(1 << n) - 1){
            if(!con[S] || (S & stable)) continue;
            for(int T = S;T;T = (T - 1) & S){
                if(lowbit(S) == lowbit(T) && ok(S - T,T)) cof[S] -= cof[S - T] * ans[T] * iP[cross(ext[0][S - T],T) + cross(ext[0][T],S - T)]; 
            }
            for(int T = S;T;T = (T - 1) & S){
                if(ok(S - T,T)) dp[S] += dp[S - T] * cof[T] * iP[cross(ext[0][S - T],T)];
                //S - T 必须合法，即 dp[S - T]=1，但实测删去不会出问题
            }
            //由于每个连通块只能有一个点，故需特判 ok(S - T,T)
            //若 u,v 包含在 S 中但不是同一个强连通分量，且不存在边 u->v，则不能存在 u->w->v，
            //其中 w 和 u 为同一连通块，且必有 u->w，故有以上转移
            ans[S] = 1 - dp[S];
            cof[S] += ans[S];
            dp[S] += ans[S];
            //dp[S] ∈ {0,1}
        } 
        //ans[S]：S 在每一个连通块只包含一个强连通分量，且缩点后为孤点的概率
        rep(S,0,(1 << n) - 1){
            g[S] = 0;
            if(!con[S] || (S & stable)) continue;
            int ssum = 0;
            rep(u,0,n - 1){
                if((ext[0][S] >> u) & 1) continue;
                if((ext[1][S] >> u) & 1) ssum += popcnt(msk[u] & S);      
            }       
            g[S] = iP[ssum] * ans[S];
            //g[S]：同时满足 Part 2&4 的概率
        }
        cof[0] = 1;
        rep(S,1,(1 << n) - 1){
            int u = ctz(S);
            cof[S] = cof[S - (bel[0][u] & S)] * res[(bel[0][u] & S)];
        }
        //cof与之前的含义不同，为 S 中的点均在之前为关键点的概率
        rep(S,0,(1 << n) - 1){
            f[S] = 0;
            if(!con[S] || (S & stable)) continue;
            int SS = ext[1][S],fail = 0;
            rep(u,0,n - 1) if(((SS >> u) & 1) && (S & bel[0][u]) == 0) fail = 1;
            f[S] = 1 - fail;
        }
        // S 是否包含合并上的每一个连通块
        per(S,(1 << n) - 1,0){
            if(S & stable) continue;
            for(int T = S - lowbit(S);T;T = (T - 1) & S) if(ok(S - T,T)) f[T] -= iP[cross(S - T,ext[0][T])] * f[S] * cof[S - T];
        }
        //统计路径，每次加入一个新的连通块
        rep(S,0,(1 << n) - 1) f[S] *= cof[S];
        //路径的起始点的权值也要乘上去
        rep(S,0,(1 << n) - 1) tf[S] = 0;
        rep(S,0,(1 << n) - 1){
            if((S & stable)) continue;
            for(int T = S;T;T = (T - 1) & S) if(ok(S - T,T)) tf[T] += f[S];
        }
        rep(S,0,(1 << n) - 1) if((S & stable) == 0) res[S] = tf[S] * g[S];
    }
    Z answer = 0;
    rep(S,1,(1 << n) - 1) answer += res[S];
    printf("%d\n",answer.val());
}