「雅礼day5/jzoj5398」崇拜Adore - 状态压缩+动态规划

题目大意

小w 偶然间见到了一个 DAG。
这个 DAG 有 m 层，第一层只有一个源点，最后一层只有一个汇点，剩下的每一层都有 k 个节点。
现在小 w 每次可以取反第 i(1 < i < n - 1) 层和第 i + 1 层之间的连边。也就是把原本从(i, k1) 连到 (i + 1, k2) 的边，变成从 (i, k2) 连到 (i + 1, k1)。
请问他有多少种取反的方案，把从源点到汇点的路径数变成偶数条？
答案对 998244353 取模。

---

题目分析

为了方便，下文使用记号$(i,x)$表示第$i$层的第$x$个点。

$k$很小，所以可以对每一层的点进行状态压缩。
设状态$f[i,j]$表示前$i$行，第$i$行的状态是$j$的方案数。
其中状态是这样设置的：用二进制位分别表示到达$(i,x)$的路径数的奇偶性，若到达$(i,x)$有奇数条路径则第$x$位是$1$。

若当前到达$(i,x)$的路径数为奇数，而有从$(i,x)$到达$(i+1,y)$的边，则此时到达$(i+1,y)$的路径数便也是奇数。
根据第$i$行的状态$j$，再根据连接到$i+1$层的边，我们可以确定出第$i+1$行的状态：
设$(i,x)$不取反能够到达的点的集合为$a[x]$，枚举每一位$K$，若$j\&a[K]$有奇数个$1$，说明到达$(i+1,K)$的路径数为奇数，将转移到的$i+1$行的状态第$K$位置为$1$。

取反同理，不赘述了。

到最后一行的时候状态中不能包含奇数，因此$($末行转移状态$S\&$倒数第二行状态$j)$仅有偶数个$1$的时候才能统计答案。

注意第一行和最后一行比较特殊，放在循环外处理。预处理出每一个状态所包含的$1$的个数。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const LL mod=998244353;
LL f[2][(1<<10)+5],ans=0;
int n,k,s1,s2,g[(1<<10)+5],a[15],b[15];
int main() {
	n=Get_Int();
	k=Get_Int();
	for(int i=0; i<k; i++)s1|=Get_Int()<<i;
	for(int i=0; i<(1<<k); i++)g[i]=g[i>>1]^i&1;
	f[0][s1]=1;
	for(int i=1; i<n-2; i++) {
		memset(f[i&1],0,sizeof(f[i&1]));
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		for(int x=0; x<k; x++)
			for(int y=0; y<k; y++) {
				int tmp=Get_Int();
				a[x]|=tmp<<y;
				b[y]|=tmp<<x;
			}
		for(int j=0; j<(1<<k); j++)
			if(f[(i-1)&1][j]) {
				int x=0,y=0;
				for(int K=0; K<k; K++) {
					x|=g[j&a[K]]<<K;
					y|=g[j&b[K]]<<K;
				}
				f[i&1][x]=(f[i&1][x]+f[(i-1)&1][j])%mod;
				f[i&1][y]=(f[i&1][y]+f[(i-1)&1][j])%mod;
			}
	}
	for(int i=0; i<k; i++)s2|=Get_Int()<<i;
	for(int i=0; i<(1<<k); i++)
		if(!g[s2&i])ans=(ans+f[(n-3)&1][i])%mod;
	printf("%lld\n",ans);
	return 0;
}