题解：P11834 [省选联考 2025] 岁月

· · 题解

C 性质

不妨将概率计数转为方案计数，最后再乘上 2^{-2m}。

所有边权相等，条件可以转化为存在一棵外向生成树，考虑所有可以成为根的节点，可以发现其组成一个 SCC，更具体的，其恰好是缩点后唯一入度为 0 的 SCC。

因此我们设 dp_S 表示集合 S 恰好是缩点后唯一入度为 0 的 SCC 方案数，答案即为 \sum dp_S。

首先要保证 S 为一个 SCC，设集合 S 构成一个 SCC 的方案数 f_S，这就是主旋律，考虑用总的方案数减去不合法方案数。

不合法的方案数等价于缩点后有多个点，并且形成了一个 DAG，因此可以仿照 DAG 容斥的方法，每次删去入度为 0 的 SCC。

设 g_S 表示将 S 划分为若干个入度为 0 的 SCC 方案数，且包含容斥系数，容易推导出容斥系数为 (-1)^{k+1} ，k 为 SCC 的个数，转移时要钦定 \operatorname{lowbit(S)}\in T。

g_S = f_S - \sum\limits_{T \subseteq S,\operatorname{lowbit(S)}\in T} f_Tg_{S-T} $$f_S = 4^{E(S)} -\sum\limits_{T \subset S} g_T2^{E(T,S-T)}4^{E(S-T)}$$ 其中 $E(S)$ 表示 $S$ 内部无向边的数量，$E(S,T)$ 表示两端分别在 $S$，$T$ 的无向边数量。$E(S)$ 容易 $O(2^nn)$ 求出，$E(S,T) = E(S + T)-E(S)-E(T)$。 最后考虑容斥计算 $dp_S$，记全集为 $U$。我们枚举 $T\subset U-S$，钦定 $T$ 中存在若干入度为 $0$ 的 SCC，发现容斥系数恰好为 $(-1)^k$ 即为 $-g_T$。 对于剩下的边，$S+T$ 可以向 $U-S-T$ 连边，$U-S-T$ 中可以任意连边。 $$dp_S = \sum\limits_{T \subset S-T} -f_Sg_T2^{E(S+T,U-S-T)}4^{E(U-S-T)}$$ 至此我们在 $O(3^n)$ 时间复杂度内解决了 C 性质。 ### 正解 考虑 Kruskal 的过程，按边权从小到大合并连通块。显然在加入 $\le w$ 的边后，对于每个在原无向图中的连通块，其在有向图中也一定存在一个根集可以到达这个连通块的所有点。 因此我们有这样一种做法，从小到大扫描边权 $w$，维护目前每个点集 $S$ 表示 $S$ 恰好为当前所在连通块根集的方案数 $dp_S$。加入所有边权为 $w$ 的边时，合并所有连通块，合并根集更新 $dp_S$。 考虑如何合并根集合，我们称一条边是关键边，当且仅当其终点属于根集。那么把连通块看作点，只保留关键边，合并的根集就是新图上最小外向生成树的根集。 因此新问题类似于 C 性质，我们对于每次新合并的连通块跑一遍 C 性质即可，额外的，由于要从 $dp_T$ 推出 $dp_S$，每个连通块内的根集已经为其原本所在连通块的根集，要考虑这部分对转移的影响。 一些定义： * $ext_S$ 表示集合 $S$ 所处原本连通块集合的并。 * $ent_S$ 表示合并连通块后集合 $S$ 所处连通块集合。 * $f_S$ 表示 $S$ 为 $ext_S$ 根集的方案数。 * $g_S$ 表示将 $S$ 在新图上划分为若干个 $0$ 入度 SCC 方案数，且包含容斥系数。 * $dp_S$ 表示 $S$ 为 $ent_S$ 根集的方案数。 * $dp_S'$ 表示原本连通块的 $dp_S$。 考虑 $g_S$ 的转移，注意 $ext_{T}$ 与 $ext_{S-T}$ 之间可以连非关键边。 $$g_S = f_S - \sum\limits_{T \subseteq S,\operatorname{lowbit(S)}\in T} ok(T,S-T)f_Tg_{S-T}+2^{D(T,S-T)}$$ $ok(S,T)$ 表示 $ext_S,ext_T$ 在新图上不能有交集，$D(S,T)$ 表示在根集为 $S$，$T$ 情况下 $ext_S$ 与 $ext_T$ 之间的非关键边。 $$D(S,T)=E(S,ext_T-T)+E(ext_S-S,T)+E(ext_S-S,ext_T-T) \times 2$$ 考虑 $f_S$ 的转移，由于需要计算 $ext_S$ 的总方案数，设 $cof_S$ 表示保证 $S$ 分别为原本每个连通块根集情况下任意连边的总方案数，可以递推计算，设 $T= ext_{lowbit(S)}\& S$，$cof_S= cof_{S-T}dp_T'4^{E(ext_{S-T},ext_T)}$。 $f_S$ 转移时注意 $ext_{S-T}$ 可以向 $ext_T-T$ 连非关键边。 $$f_S = cof_S -\sum\limits_{T \subset S}ok(T,S-T) g_Tcof_{S-T}2^{E(ext_T,ext_{S-T})+E(ext_{S-T},ext_T-T)}$$ 考虑 $dp_S$ 的转移，记全集 $U=ent_S$，为了方便表述，设 $A=U-ext_{S+T}$，$A$ 之间可以任意连边，设其方案数为 $con_S$，可以递推计算。 对于每个原本的连通块，$con_S = \sum\limits_{T \subset S} dp_S'$。 对于若干个原本连通块的并，设 $T= ext_{lowbit(S)}$，$con_S= con_{S-T}con_T4^{E(ext_{S-T},ext_T)}$。 $dp_S$ 转移时注意 $ext_{S}$ 与 $ext_{T}$ 之间可以连非关键边，$A$ 可以向 $ext_{S+T}-S-T$ 连非关键边。 $$dp_S = \sum\limits_{T \subset S-T} -ok(S,T)ok(S,A)f_Sg_Tcon_{A}2^{E(ext_{S+T},A)+D(S,T)+E(A,ext_{S+T}-S-T)}$$ 最终答案即为 $\sum dp_S

注意除了关键边和非关键边，还有在连通块内部的边，这种边不会影响连通性，可以直接给答案 \times 4。

由于我们只在新合并连通块时枚举子集，因此时间复杂度不超过 \sum\limits_{i=1}^n 3^i，总时间复杂度 O(3^n)。

代码

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=215,M=(1<<15)+5,mo=1e9+7;
struct edge{
    int u,v;
};
int c,T,n,m,U,ans;
int p[N],ed[N],fa[N],fa2[N],msk[N];
int sum[M],f[M],g[M],dp[M],ent[M],ext[M],cof[M],con[M];
vector<edge>e[N];
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k;
}
int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1)
            res=res*x%mo;
        x=x*x%mo;
        y=y>>1;
    }
    return res;
}
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int find2(int x){
    return fa2[x]==x?x:fa2[x]=find2(fa2[x]);
}
int ppc(int x){
    return __builtin_popcountll(x);
}
int ctz(int x){
    return __builtin_ctzll(x);
}
int qsum(int x,int y){
    return sum[x^y]-sum[x]-sum[y];
}
int nsum(int x,int y){
    return (qsum(x,ext[y]^y)+qsum(ext[x]^x,y)+qsum(ext[x]^x,ext[y]^y)*2);
}
int ok(int x,int y){
    return (ext[x]&ext[y])==0;
}
bool check(int x){
    return (ent[1<<ctz(x)]&x)!=x||ext[1<<ctz(x)]==ent[x];
}
void work(){
    for(int s=1;s<(1<<n);s++){
        if(check(s)) continue;
        int t=(ext[1<<ctz(s)]&s);
        cof[s]=cof[s^t]*dp[t]%mo*p[qsum(ext[s^t],ext[t])*2]%mo;
        if(ext[s]==s){
            t=ext[1<<ctz(s)];
            if(s==t){
                con[s]=0;
                for(int t=s;t;t=((t-1)&s))
                    con[s]=(con[s]+cof[t])%mo;
            }
            else
                con[s]=con[s^t]*con[t]%mo*p[qsum(s^t,t)*2]%mo;
        }
    }
    for(int s=1;s<(1<<n);s++){
        if(check(s)) continue;
        g[s]=0,f[s]=cof[s];
        for(int t=((s-1)&s);t;t=((t-1)&s))
            if(ok(t,s^t)&&lowbit(t)==lowbit(s))
                g[s]=(g[s]-f[t]*g[s^t]%mo*p[nsum(t,s^t)])%mo;
        for(int t=s;t;t=((t-1)&s))
            if(ok(t,s^t))
                f[s]=(f[s]-g[t]*cof[s^t]%mo*p[qsum(ext[t]^t,ext[s^t])+qsum(ext[t],ext[s^t])])%mo;
        g[s]=(g[s]+f[s])%mo;
    }
    for(int s=1;s<(1<<n);s++){
        if(check(s)) continue;
        U=ent[s],dp[s]=0;
        for(int t=s^U;;t=((t-1)&(s^U))){
            if(ok(s,t)&&ok(s,U^ext[s^t]))
                dp[s]=(dp[s]-f[s]*g[t]%mo*con[U^ext[s^t]]%mo*p[nsum(s,t)+qsum(ext[s^t]^s^t,U^ext[s^t])+qsum(ext[s^t],U^ext[s^t])])%mo;
            if(!t) break;
        }
    }
}
void solve(){
    int u,v,w;
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        u=read(),v=read(),w=read();
        e[w].push_back((edge){u-1,v-1});
    }
    dp[0]=1,g[0]=-1,cof[0]=1,con[0]=1;
    for(int s=1;s<(1<<n);s++)
        ent[s]=s,dp[s]=0,cof[s]=0,con[s]=0;
    for(int i=0;i<n;i++){
        fa[i]=i,fa2[i]=i;
        msk[i]=(1<<i),dp[1<<i]=1,cof[1<<i]=1,con[1<<i]=1;
    }
    int res=1;
    for(int l=1;l<=m;l++){
        int stt=0;
        for(edge i:e[l]){
            u=find(i.u),v=find(i.v);
            if(u==v)
                res=res*4%mo;
            else{
                stt=1;
                ed[i.u]|=(1<<i.v),ed[i.v]|=(1<<i.u);
                u=find2(i.u),v=find2(i.v);
                if(u!=v){
                    fa2[v]=u;
                    msk[u]|=msk[v];
                }
            }
        }
        if(!stt) continue;
        for(int s=1;s<(1<<n);s++){
            int t=ctz(s);
            sum[s]=sum[s^(1<<t)]+ppc(ed[t]&s);
        }
        for(int s=1;s<(1<<n);s++){
            ext[s]=ent[s],ent[s]=0;
            for(int i=0;i<n;i++)
                if(s&(1<<i))
                    ent[s]|=(msk[find2(i)]);
        }
        work();
        for(int i=0;i<n;i++)
            fa[i]=fa2[i],ed[i]=0;
    }
    ans=0;
    for(int s=1;s<(1<<n);s++)
        ans=(ans+res*dp[s])%mo;
    ans=ans*qpow(p[2*m],mo-2)%mo;
    ans=(ans+mo)%mo;
    printf("%lld\n",ans);
    for(int i=1;i<=m;i++)
        e[i].clear();
}
signed main(){
    c=read(),T=read();
    p[0]=1;
    for(int i=1;i<=210;i++)
        p[i]=p[i-1]*2%mo;
    while(T--)
        solve();
    return 0;
}