专栏文章

题解：CF1210F1 Marek and Matching (easy version)

LLastKismet
CF1210F1题解参与者 1已保存评论 0

文章操作

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

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

sol

是一个 O(32n)O(3^{2n}) 的做法。
考虑霍尔定理，完美匹配要求任意左部点集合 SS 满足 ∣S∣≤∣N(S)∣|S|\le |N(S)|，N(S)N(S) 为与 SS 相连的右部点集合。
考虑容斥。考虑对每个不合法状态都设计一个唯一的代表元，以方便容斥。设 f(S,T)f(S,T) 表示 S,TS,T 可以完美匹配的概率，那么就只需要用 T=N(S)T=N(S) 的概率减去其中存在 S′⊂S,T′⊂T∧T′=N(S)S'\subset S,T'\subset T\land T'=N(S) 满足 ∣S′∣>∣T′∣|S'|>|T'| 的概率即可。
考虑对每一种不合法状态确定一对满足上述不合法条件的 S,TS,T 作为代表元，这样容斥时可以直接枚举代表元转移。我们找 ∣S∣−∣T∣|S|-|T| 最大的一对 S,TS,T 使得其余部分可以完美匹配即可，如果有多种，选择 ∣S∣|S| 最小的。这样的一对 S,TS,T 必然是唯一的。有证明：
假如存在两对 S,TS,T 上面两个条件均相等，分类讨论：
  1. 若 S1,S2S_1,S_2 无交，那么 S1∪S2,T1∪T2S_1\cup S_2,T1\cup T2 显然不劣。
  2. 若 S1,S2S_1,S_2 有交，那么 S1∩S2S_1\cap S_2 或 S1∪S2S_1\cup S_2 不劣。因为 ∣S1∣−∣T1∣+∣S2∣−∣T2∣=∣S1∪S2∣−∣T1∪T2∣+∣S1∩S2∣−∣N(S1∩S2)∣≤∣S1∪S2∣−∣T1∪T2∣+∣S1∩S2∣−∣T1∩T2∣|S_1|-|T_1|+|S_2|-|T_2|\\=|S1\cup S2|-|T_1\cup T_2|+|S_1\cap S_2|-|N(S_1\cap S_2)|\\\le|S1\cup S2|-|T_1\cup T_2|+|S_1\cap S_2|-|T1\cap T2| 如果取等那么取交 ∣S∣|S| 更小，否则必有一个更优。
因此考虑设 g(S,T)g(S,T) 为只考虑 S,TS,T 导出子图时 S,TS,T 为代表元的情况，容斥掉存在更小代表元的情况即可。注意仍需满足 T=N(S)T=N(S)。记 c(S,T)c(S,T) 为 T=N(S)T=N(S) 的概率，d(S,T)d(S,T) 为 S,TS,T 无连边的概率。有转移式：
g(S,T)=c(S,T)−∑S′⊂S∑T′⊂Tg(S′,T′)d(S′,T∖T′)f(S∖S′,T∖T′)[∣S′∣−∣T′∣≥∣S∣−∣T∣]g(S,T)=c(S,T)-\sum_{S'\subset S}\sum_{T'\subset T}g(S',T')d(S',T\setminus T')f(S\setminus S',T\setminus T')[|S'|-|T'|\ge |S|-|T|]
d(S′,T∖T′)d(S',T\setminus T') 是因为需要保证 T=N(S)T=N(S)，f(S∖S′,T∖T′)f(S\setminus S',T\setminus T') 是因为其余部分应当可以完美匹配，[∣S′∣−∣T′∣≥∣S∣−∣T∣][|S'|-|T'|\ge |S|-|T|] 是因为要满足上述条件。
然后考虑转移 ff，基本同理，就不额外解释各项意义了：
f(S,T)=c(S,T)−∑S′⊂S∑T′⊂Tg(S′,T′)d(S′,T∖T′)f(S∖S′,T∖T′)f(S,T)=c(S,T)-\sum_{S'\subset S}\sum_{T'\subset T}g(S',T')d(S',T\setminus T')f(S\setminus S',T\setminus T')

code

CPP
int n;
mint p[N][N],c[1<<N][1<<N],d[1<<N][1<<N],f[1<<N][1<<N],g[1<<N][1<<N];
#define popc(s) __builtin_popcount(s)
 
inline void Main(){
    cin>>n;
    repl(i,0,n)repl(j,0,n)cin>>p[i][j],p[i][j]/=100;
    repl(s,0,1<<n)repl(t,0,1<<n){
        c[s][t]=d[s][t]=1;
        if(!s)continue;
        repl(j,0,n)if(t>>j&1){
            mint v=1;repl(i,0,n)if(s>>i&1)v*=1-p[i][j];
            c[s][t]*=1-v,d[s][t]*=v;
        }
    }
    repl(s,0,1<<n)repl(t,0,1<<n){
        if(popc(s)<=popc(t)){
            f[s][t]=c[s][t];
            for(int ss=s-1&s;~ss;ss=ss?ss-1&s:-1)for(int tt=t-1&t;~tt;tt=tt?tt-1&t:-1)
                f[s][t]-=g[ss][tt]*d[ss][t^tt]*f[s^ss][t^tt];
        }else{
            g[s][t]=c[s][t];
            for(int ss=s-1&s;~ss;ss=ss?ss-1&s:-1)for(int tt=t-1&t;~tt;tt=tt?tt-1&t:-1)
                if(popc(ss)-popc(tt)>=popc(s)-popc(t))g[s][t]-=g[ss][tt]*d[ss][t^tt]*f[s^ss][t^tt];
        }
    }
    put(f[(1<<n)-1][(1<<n)-1]);
}

评论

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

正在加载评论...