专栏文章

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

fflower1
P11834题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@minvbe1o
此快照首次捕获于
2025/12/02 08:56
3 个月前
此快照最后确认于
2025/12/02 08:56
3 个月前
查看原文

C 性质

不妨将概率计数转为方案计数，最后再乘上 2−2m2^{-2m}。
所有边权相等，条件可以转化为存在一棵外向生成树，考虑所有可以成为根的节点，可以发现其组成一个 SCC，更具体的，其恰好是缩点后唯一入度为 00 的 SCC。
因此我们设 dpSdp_S 表示集合 SS 恰好是缩点后唯一入度为 00 的 SCC 方案数，答案即为 ∑dpS\sum dp_S。
首先要保证 SS 为一个 SCC，设集合 SS 构成一个 SCC 的方案数 fSf_S，这就是主旋律，考虑用总的方案数减去不合法方案数。
不合法的方案数等价于缩点后有多个点，并且形成了一个 DAG，因此可以仿照 DAG 容斥的方法，每次删去入度为 00 的 SCC。
设 gSg_S 表示将 SS 划分为若干个入度为 00 的 SCC 方案数，且包含容斥系数，容易推导出容斥系数为 (−1)k+1(-1)^{k+1} ，kk 为 SCC 的个数，转移时要钦定 lowbit(S)⁡∈T\operatorname{lowbit(S)}\in T。
gS=fS−∑T⊆S,lowbit(S)⁡∈TfTgS−Tg_S = f_S - \sum\limits_{T \subseteq S,\operatorname{lowbit(S)}\in T} f_Tg_{S-T}
fSf_S 转移时枚举 TT，钦定 TT 中形成若干个入度为 00 的 SCC。对于剩下的边， TT 可以向 S−TS-T 连边，S−TS-T 中可以任意连边。
fS=4E(S)−∑T⊂SgT2E(T,S−T)4E(S−T)f_S = 4^{E(S)} -\sum\limits_{T \subset S} g_T2^{E(T,S-T)}4^{E(S-T)}
其中 E(S)E(S) 表示 SS 内部无向边的数量，E(S,T)E(S,T) 表示两端分别在 SS，TT 的无向边数量。E(S)E(S) 容易 O(2nn)O(2^nn) 求出，E(S,T)=E(S+T)−E(S)−E(T)E(S,T) = E(S + T)-E(S)-E(T)。
最后考虑容斥计算 dpSdp_S，记全集为 UU。我们枚举 T⊂U−ST\subset U-S，钦定 TT 中存在若干入度为 00 的 SCC，发现容斥系数恰好为 (−1)k(-1)^k 即为 −gT-g_T。
对于剩下的边，S+TS+T 可以向 U−S−TU-S-T 连边，U−S−TU-S-T 中可以任意连边。
dpS=∑T⊂S−T−fSgT2E(S+T,U−S−T)4E(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(3n)O(3^n) 时间复杂度内解决了 C 性质。

正解

考虑 Kruskal 的过程，按边权从小到大合并连通块。显然在加入 ≤w\le w 的边后，对于每个在原无向图中的连通块，其在有向图中也一定存在一个根集可以到达这个连通块的所有点。
因此我们有这样一种做法，从小到大扫描边权 ww，维护目前每个点集 SS 表示 SS 恰好为当前所在连通块根集的方案数 dpSdp_S。加入所有边权为 ww 的边时，合并所有连通块，合并根集更新 dpSdp_S。
考虑如何合并根集合，我们称一条边是关键边，当且仅当其终点属于根集。那么把连通块看作点，只保留关键边，合并的根集就是新图上最小外向生成树的根集。
因此新问题类似于 C 性质，我们对于每次新合并的连通块跑一遍 C 性质即可，额外的，由于要从 dpTdp_T 推出 dpSdp_S，每个连通块内的根集已经为其原本所在连通块的根集，要考虑这部分对转移的影响。
一些定义：
  • extSext_S 表示集合 SS 所处原本连通块集合的并。
  • entSent_S 表示合并连通块后集合 SS 所处连通块集合。
  • fSf_S 表示 SS 为 extSext_S 根集的方案数。
  • gSg_S 表示将 SS 在新图上划分为若干个 00 入度 SCC 方案数，且包含容斥系数。
  • dpSdp_S 表示 SS 为 entSent_S 根集的方案数。
  • dpS′dp_S' 表示原本连通块的 dpSdp_S。
考虑 gSg_S 的转移，注意 extText_{T} 与 extS−Text_{S-T} 之间可以连非关键边。
gS=fS−∑T⊆S,lowbit(S)⁡∈Tok(T,S−T)fTgS−T+2D(T,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)ok(S,T) 表示 extS,extText_S,ext_T 在新图上不能有交集，D(S,T)D(S,T) 表示在根集为 SS，TT 情况下 extSext_S 与 extText_T 之间的非关键边。
D(S,T)=E(S,extT−T)+E(extS−S,T)+E(extS−S,extT−T)×2D(S,T)=E(S,ext_T-T)+E(ext_S-S,T)+E(ext_S-S,ext_T-T) \times 2
考虑 fSf_S 的转移，由于需要计算 extSext_S 的总方案数，设 cofScof_S 表示保证 SS 分别为原本每个连通块根集情况下任意连边的总方案数，可以递推计算，设 T=extlowbit(S)&ST= ext_{lowbit(S)}\& S，cofS=cofS−TdpT′4E(extS−T,extT)cof_S= cof_{S-T}dp_T'4^{E(ext_{S-T},ext_T)}。
fSf_S 转移时注意 extS−Text_{S-T} 可以向 extT−Text_T-T 连非关键边。
fS=cofS−∑T⊂Sok(T,S−T)gTcofS−T2E(extT,extS−T)+E(extS−T,extT−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)}
考虑 dpSdp_S 的转移，记全集 U=entSU=ent_S，为了方便表述，设 A=U−extS+TA=U-ext_{S+T}，AA 之间可以任意连边，设其方案数为 conScon_S，可以递推计算。
对于每个原本的连通块，conS=∑T⊂SdpS′con_S = \sum\limits_{T \subset S} dp_S'。
对于若干个原本连通块的并，设 T=extlowbit(S)T= ext_{lowbit(S)}，conS=conS−TconT4E(extS−T,extT)con_S= con_{S-T}con_T4^{E(ext_{S-T},ext_T)}。
dpSdp_S 转移时注意 extSext_{S} 与 extText_{T} 之间可以连非关键边，AA 可以向 extS+T−S−Text_{S+T}-S-T 连非关键边。
dpS=∑T⊂S−T−ok(S,T)ok(S,A)fSgTconA2E(extS+T,A)+D(S,T)+E(A,extS+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)}
最终答案即为 ∑dpS\sum dp_S
注意除了关键边和非关键边，还有在连通块内部的边，这种边不会影响连通性，可以直接给答案 ×4\times 4。
由于我们只在新合并连通块时枚举子集，因此时间复杂度不超过 ∑i=1n3i\sum\limits_{i=1}^n 3^i，总时间复杂度 O(3n)O(3^n)。

代码

CPP
#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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...