一张有向无环图被分成了$m$层,第一层只有一个源点,最后一层只有一个汇点,剩下的每一层都有$k$个节点。
我们将第$i$层的第$k$个结点称作$(i,k)$。
现在你可以取反第$i(1<i<m-1)$层和第$i+1$层之间的所有连边。
也就是把原本从$(i,k_1)$连到$(i+1,k_2)$的边,全部变成从$(i,k_2)$连到$(i+1,k_1)$。
你可以任意选择一些相邻层之间的边取反,也可以都不取反。
请问他有多少种取反的方案,把从源点到汇点的路径数变成偶数条?
答案对$998244353$取模。
第一行两个整数$m,k$。
接下来$m-1$行, 第一行和最后一行有$k$个整数$0$或$1$,剩下每行有$k^2$个整数$0$或$1$,第 $(j-1)×k+t$个整数表示($i,j$)到($i+1,t$)有没有边。
一行一个整数表示答案。
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
4
【数据规模及约定】
对于20%的数据,$m≤10,k≤2$。
对于40%的数据,$m≤10^3,k≤2$。
对于60%的数据,$m≤10^3,k≤5$。
对于100%的数据,$4≤m≤10^4,k≤10$。