【YBTOJ】【状压DP】图的计数

图的计数

⼀个 DAG ，这个 DAG 有 (m) 层，第⼀层只有⼀个源点，最后⼀层只有⼀个汇点，剩下的每⼀层都有 (k) 个节点。每次可以取反第 (i) 层和第 (i+1) 层之间的连边。也就是把原本从 ((i,k_1)) 连到 ((i+1,k_2)) 的边，变成从 ((i，k_2)) 连到 ((i+1,k_1))) 。请问有多少种取反的方案，把从源点到汇点的路径数变成偶数条？答案对 (998244353) 取模。

(1le mle10000)，(1le kle10).

题解

一道很恶心的题。

• 设 (f(i,j)) 表示当前在第 (i) 行，到其中某点奇偶性状态为 (j) 的方案数。
• 用 (a(i,j)) 表示第 (i) 行 (j) 号点可到达的点对应状态，同理 (b(i,j)) 表示取反后第 (i) 行 (j) 号点可到达的点对应状态。
• 求奇偶性，可以用异或来转移。
• 最后，统计最后一层的答案，并判断其奇偶性。

代码

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 1e4+5,M = (1<<10)+5,mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret=0;char ch=' ',c=getchar();
	while(!(c>='0'&&c<='9'))ch=c,c=getchar();
	while(c>='0'&&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ch=='-'?-ret:ret;
}
int n,m;
int a[N][M],b[N][M]; 
int dp[N][M];
signed main(){
	n = read() , m = read();
	for(int i = 1 ; i <= m ; i ++)
		if(read())
			a[0][0] += 1<<(i-1);
	dp[2][a[0][0]] = 1;
	for(int i = 2 ; i <= n-2 ; i ++)
		for(int k = 1 ; k <= m ; k ++)
			for(int p = 1 ; p <= m ; p ++)
				if(read())
					a[i][k] += 1<<(p-1),
					b[i][p] += 1<<(k-1);
	
	for(int i = 3 ; i <= n-1 ; i ++)
		for(int j = 0 ; j < 1<<m ; j ++)
			if(dp[i-1][j]){
				int s1 = 0,s2 = 0;
				for(int k = 1 ; k <= m ; k ++)
					if(j & 1<<(k-1))
						s1 ^= a[i-1][k] , s2 ^= b[i-1][k];
				(dp[i][s1] += dp[i-1][j]) %= mod,
				(dp[i][s2] += dp[i-1][j]) %= mod;
//				printf(" dp[%d][%d] += [%d][%d](%d)
",i,s1,i-1,j,dp[i-1][j]);
//				printf(" dp[%d][%d] += [%d][%d](%d)
",i,s2,i-1,j,dp[i-1][j]);
			}
//	puts("");
	for(int i = 1 ; i <= m ; i ++)
		if(read())
			a[n-1][0] += 1<<(i-1);
	int ans = 0;
	for(int j = 0 ; j < 1<<m ; j ++){
		int tot = 0;
		for(int i = 1 ; i <= m ; i ++)
			if((a[n-1][0] & (1<<(i-1))) && (j & (1<<(i-1)))) tot ^= 1;
		if(!tot) 
			(ans += dp[n-1][j]) %= mod;
	}
	printf("%d",ans);
}