（非公共题目）

问题描述

　　小 w 偶然间⻅到了一个 DAG。这个 DAG 有 m 层，第一层只有一个源点，最后一层只有一个汇点，剩下的每一层都有 k 个节点。

　　现在小 w 每次可以取反第 i（1 < i < n − 1） 层和第 i + 1 层之间的连边。也就是把原本从（i, k₁ ） 连到 （i+1, k₂ ） 的边,变成从 （i , k₂ ） 连到 （i+1, k₁）。请问他有多少种取反的方案，把从源点到汇点的路径数变成偶数条？

　　答案对 998244353 取模。

输入格式

　　一行两个整数 m，k。

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

输出格式

　　一行一个整数表示答案。

样例输入

5 31 0 10 1 0 1 1 0 0 0 10 1 1 1 0 0 0 1 10 1 1

样例输出

4

数据规模与约定

20% 的数据满足 n ≤ 10，k ≤ 2。

40% 的数据满足 n ≤ 10³，k ≤ 2。

60% 的数据满足 m ≤ 10³，k ≤ 5。

100% 的数据满足 4 ≤ m ≤ 10⁴，k ≤ 10。

题解：

　　首先发现k ≤ 10，可以状态压缩。我们设dp[i][j]代表到了i行，当前行的状态为j的情况下的方案数。状态中的0和1代表当前行的每一个点，上面到这一个点的路径的条数的奇偶。

　　我们预处理一个数组orz[i]代表i这个数的状态，也就是i这个数的二进制位上1的个数的奇偶。这个可以递推不用一个一个求。

　　然后dp初值自然就是源点到第2层的状态了（第一层为源点）。把源点向i如果有连边，那么s|=(1<<i)。然后dp[1][s]=1。

　　对于中间的层数，我们枚举所有的状态1~2¹⁰-1。然后进行转移，设a[i]代表当前这两层下面的那一层的第i个点，可以从上面哪一个点来，压缩一下，例如a[2]=5(101)代表上一层的点1和3有连向这一层的点2的一条边。然后我们设一个集合S=0。对于这一层的每一个点i。如果上一层的状态status，与（&）上这一个点的a[i]，可以不能转移的自然就变成0了。到上一层的点的路径的奇偶状态转移到了这一个点，如果相加为奇数，也就是orz[status&a[i]]=1，的话代表到这一个点的路径的条数为奇数，那么集合S|=(1<<i)即可，S就是这一层的状态，我们一个一个的填进去。然后dp[i][S]+=dp[i-1][status]。取个模就可以了。然后对于题目中所说的“取反”的边，同样使用一个b[i]来存开一个SS=0来存同样转移即可了。

　　最后只要统计有哪些点连向汇点，就可以枚举n-1层所有可能的状态，如果status&s的orz是偶数，那么就可以ans+=dp[n-1][s]。

　　数组滚滚Great！

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define RG register 8 #define LL long long 9 #define fre(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);10 using namespace std;11 const int MAXN=11000,mod=998244353;12 int n,k,ans,s;13 int dp[2][(1<<10)+8],orz[(1<<10)+8];14 int main()15 {16 fre("adore");17 scanf("%d%d",&n,&k);18 int All=(1<
           
            >1]^(i&1);21 for(int i=0,x;i