题解：P6789 寒妖王

· · 题解

Solution

我自己做的时候先设计了一个极为抽象的 DP，但是发现不同点集之间完全不独立，浪费了一晚上的时间呜呜。概率 DP 一定要考虑概率是否独立啊啊啊。

基环树这个东西具有拟阵的性质，所以可以贪心。

对于每条边，只保留优先级比他高的边，选出一个边集。对于每个边集，判断这条边能否加入，计算概率即可。

这条边能加入：

  1. 两个端点在同一个连通块内，且这个连通块是一棵树。
  2. 两个端点在不同的连通块内，且这两个连通块至少有一个是树。

现在你要算一个点集有多大概率是一个极大的连通块。这个东西用集合幂级数 ln + 子集卷积 + 矩阵树定理可以做到 O(m \text{poly}(n) 2^n)，但是我怀疑它跑不过 O(m 3^n)。

设 cnt_S 为考虑 S 的导出子图，有多少种方法使他成为一棵树。直接枚举一条边，将 S 拆分为两个子集即可。

设 Cnt_S 为考虑 S 的导出子图，有多少种方法使他连通。用所有图（2^e）减去钦定了某一个包含 \rm lowbit 的连通块即可。

不过这样会 T 飞起。你发现并不需要每次都跑一遍全局的树、图计数。新加入一条边 (u,v)，只去修改 \{u,v\} \subseteq S 的 S 即可，这样拥有更小的常数。

其实这两个过程都可以直接用子集卷积优化的，所以其实直接做就是 O(m n^2 2^n) 的了？但是懒得写啊呜呜呜。

统计答案的时候再枚举一次子集。唉这个题看起来这么唐，怎么坠机了呢。 /ll

#include<bits/stdc++.h>
#define ll long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXM=60+5,MAXS=(1<<15)+10,MOD=998244353,_2=(MOD+1)/2;
int n,m,ans,f[MAXS],g[MAXS],cnt[MAXS],pw[MAXM];
struct Edge {int u,v,w;}e[MAXM];
ll qpow(ll base,int p) {
    ll ans=1;
    while(p) {
        if(p&1) ans=ans*base%MOD;
        base=base*base%MOD,p>>=1;
    }
    return ans;
}
void solve(int id) {
    int prob=0;
    int u=e[id].u,v=e[id].v;
    ffor(s,0,(1<<n)-1) if(s&(1<<u-1)) {
        int ot=(1<<n)-1-s;
        for(int S=ot;S;S=(S-1)&ot) if(S&(1<<v-1)) prob=(prob+(-1ll*f[s]*f[S]%MOD+1ll*f[s]*g[S]%MOD+1ll*g[s]*f[S]%MOD)%MOD*pw[cnt[(1<<n)-1-s-S]])%MOD;
    }
    ffor(s,0,(1<<n)-1) if((s&(1<<u-1))&&(s&(1<<v-1))) prob=(prob+1ll*f[s]*pw[cnt[(1<<n)-1-s]])%MOD;
    ans=(ans+1ll*prob*qpow(pw[id],MOD-2)%MOD*e[id].w)%MOD;
    ffor(i,0,(1<<n)-1) {
        if((i&(1<<u-1))&&(i&(1<<v-1))) {
            cnt[i]++,g[i]=2*g[i]%MOD;
            for(int s1=i;s1;s1=(s1-1)&i) {
                if(!(s1&(1<<u-1))) continue ;
                int s2=i-s1;
                if(!(s2&(1<<v-1))) continue ;
                g[i]=(g[i]+1ll*g[s1]*g[s2])%MOD;
                f[i]=(f[i]+1ll*f[s1]*f[s2])%MOD;
            }
        }
    }
    return ;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    ffor(i,1,m) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,[](Edge A,Edge B) {
        return A.w>B.w; 
    });
    pw[0]=1; ffor(i,1,m) pw[i]=pw[i-1]*2%MOD;
    ffor(i,1,n) f[1<<i-1]=g[1<<i-1]=1;
    ffor(i,1,m) solve(i);
    cout<<(ans%MOD+MOD)%MOD;
    return 0;
}