JZOJ 5398. 【NOIP2017提高A组模拟10.7】Adore

时间:2022-12-17 14:36:48

Description

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

Input

一行两个整数m, k。
接下来m - 1 行, 第一行和最后一行有k 个整数0 或1,剩下每行有k2 个整数0 或1,第(j- 1)* k + t 个整数表示(i, j) 到(i + 1, t)有没有边。

Output

一行一个整数表示答案。

Sample Input

5 3
1 0 1
0 1 0 1 1 0 0 0 1
0 1 1 1 0 0 0 1 1
0 1 1

Sample Output

4

Data Constraint

20% 的数据满足n <= 10, k <= 2
40% 的数据满足n <= 10^3, k <= 2。
60% 的数据满足m <= 10^3, k <= 5。
100% 的数据满足4 <= m <= 10^4, k <= 10。

Solution

  • 考虑状压每⼀层的⽅案数奇偶性做 DP 。

  • F[i][j] 表示做到第 i 层、此时状态为 j 的方案数。

  • G[j] 表示状态 j 的二进制中“1”的个数的奇偶性(偶数为0,奇数为1)。则:

    G[j]=G[j>>1] xor (j and 1)

  • 即用之前 少一位的状态 异或上 这一位的奇偶性 推出 这个状态

  • 设初始层状态为 s1 ,结束层状态为 s2

  • 则显然初始状态即为 F[1][s1]=1

  • 若一个状态 i 满足 G[i and s2]=0 (即为偶数条路径),则 F[N][i] 可加入答案。

  • 至于层与层之间的转移,设出这一层(单层)的状态 a,b (交换前和交换后),

  • a,b 都可以根据本层的连边处理出来。

  • 至于转移的话,只需转移状态是奇数的情况,因为偶数不影响奇偶性(偶+偶=偶,偶+奇=奇)。

  • 时间复杂度 O(NK2K)

Code

#include<cstdio>
#include<cstring>
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
const int mo=998244353;
int roll,s1,s2;
long long ans;
int f[2][1<<10],g[1<<10];
int a[11],b[11];
inline int read()
{
int X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
int main()
{
int n=read(),k=read(),s=1<<k;
for(int i=0;i<k;i++) s1|=read()<<i;
for(int i=0;i<s;i++) g[i]=g[i>>1]^i&1;
f[0][s1]=1;
for(int i=2;i<n-1;i++)
{
clr(f[roll^=1]),clr(a),clr(b);
for(int j=0;j<k;j++)
for(int l=0;l<k;l++)
{
int x=read();
a[j]|=x<<l;
b[l]|=x<<j;
}
for(int j=0;j<s;j++)
if(f[roll^1][j])
{
for(int l=s1=s2=0;l<k;l++)
{
s1|=g[j&a[l]]<<l;
s2|=g[j&b[l]]<<l;
}
f[roll][s1]=(f[roll][s1]+f[roll^1][j])%mo;
f[roll][s2]=(f[roll][s2]+f[roll^1][j])%mo;
}
}
for(int i=s2=0;i<k;i++) s2|=read()<<i;
for(int i=0;i<s;i++)
if(!g[s2&i]) ans=(ans+f[roll][i])%mo;
printf("%lld",ans);
return 0;
}