题解：AT_abc306_h [ABC306Ex] Balance Scale

思路

题目可化为一个有

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

CPP

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

题解：AT_abc306_h [ABC306Ex] Balance Scale

文章操作

思路

Code

相关推荐

评论

题解：AT_abc306_h [ABC306Ex] Balance Scale