题解：AT_abc306_h [ABC306Ex] Balance Scale

Emplace · 2025-01-25 15:58:50 · 题解

思路

题目可化为一个有 M 条边的有向无环图。对于每一条边，进行一个定向与合并的操作。

先考虑定向。

可以用拓扑排序对图进行分层（不需要真正进行出来）。然后就可以考虑进行一个状压 DP 了。

考虑有一个集合 S，它表示已经加入图中的点，并设计状态 dp_S。再定义一个集合 T，它表示准备加入图中的点，且集合中的点无边相连与 S \cap T = \empty。

那么如果 i \in S，j \in T，就可以定一条 i \rightarrow j 的边。

但是这样会算重复，便可以在 DP 是加一个系数，(-1)^{|T|−1}。这样就可以实现容斥。

根据上面的便可推出方程式 dp_{S \cup T} = \sum_{ S\subseteq T} (-1)^{|T|−1} dp_S。

再考虑合并。

同样考虑有一个集合 S。还有一个集合 T。如果集合 T 中有两个点相连，那么可以把两个点合并，得到一个新的集合。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[200005],b[200005],f[1<<20],s[1<<20],mod=998244353,dp[1<<20];
int find(int x){
    if(x==f[x]){
        return x;
    }
    return f[x]=find(f[x]);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<1<<n;i++){
        for(int j=1;j<=n;j++){
            f[j]=j;
        }
        for(int j=1;j<=m;j++){
            if(i&(1<<a[j]-1)&&i&(1<<b[j]-1)){
                f[find(a[j])]=find(b[j]);
            }
        }
        for(int j=1;j<=n;j++){
            if(i&(1<<(j-1))&&f[j]==j){
                s[i]++;
            }
        }
    }
    dp[0]=1;
    for(int i=1;i<1<<n;i++){
        for(int j=i;j;j=(j-1)&i){
            if((s[j]-1)%2==0){
                dp[i]+=1*dp[i^j];
            }
            else{
                dp[i]+=-1*dp[i^j];
            }
            dp[i]=(dp[i]+mod)%mod;
        }
    }
    cout<<dp[(1<<n)-1];
    return 0;
}