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

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] x o r (j a n d 1)$
即用之前 少一位的状态 异或上 这一位的奇偶性 推出 这个状态。
设初始层状态为 s1 ，结束层状态为 s2 。
则显然初始状态即为 F[1][s1]=1 。
若一个状态 i 满足 G[i and s2]=0 （即为偶数条路径），则 F[N][i] 可加入答案。
至于层与层之间的转移，设出这一层（单层）的状态 a,b （交换前和交换后），
a,b 都可以根据本层的连边处理出来。
至于转移的话，只需转移状态是奇数的情况，因为偶数不影响奇偶性（偶+偶=偶，偶+奇=奇）。
时间复杂度 O(N∗K∗2K) 。

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

秒客网

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