103177: [Atcoder]ABC317 Ex - Walk

Problem Statement

We have a directed graph with $N$ vertices numbered $1$ to $N$. The graph has no multi-edges but can have self-loops. Also, every edge in the graph satisfies the following condition.

• If the edge goes from vertex $s$ to vertex $t$, then $s$ and $t$ satisfy at least one of $0 \leq t - s\leq 2$ and $t = 1$.

The presence or absence of an edge in the graph is represented by sequences $A, B, C, D$, each of length $N$. Each element of $A, B, C, D$ has the following meaning. (Let $A_n$ denote the $n$-th element of $A$; the same applies to $B_n, C_n, D_n$.)

• $A_n$ is $1$ if there is an edge from vertex $n$ to vertex $n$, and $0$ otherwise.
• $B_n$ is $1$ if there is an edge from vertex $n$ to vertex $n+1$, and $0$ otherwise. (Here, $B_N = 0$.)
• $C_n$ is $1$ if there is an edge from vertex $n$ to vertex $n+2$, and $0$ otherwise. (Here, $C_{N-1} = C_N = 0$.)
• $D_n$ is $1$ if there is an edge from vertex $n$ to vertex $1$, and $0$ otherwise. (Here, $D_1 = A_1$.)

In the given graph, find the number, modulo $998244353$, of walks with $K$ edges starting at vertex $1$ and ending at vertex $N$.

Here, a walk with $K$ edges starting at vertex $1$ and ending at vertex $N$ is a sequence of vertices $v_0 = 1, v_1, \dots, v_K = N$ such that for each $i$ $(0 \leq i \lt K)$ there is an edge from vertex $v_i$ to vertex $v_{i + 1}$. Two walks are distinguished when they differ as sequences.

Constraints

• $2 \leq N \leq 5 \times 10^4$
• $1 \leq K \leq 5 \times 10^5$
• $A_i, B_i, C_i, D_i \in \lbrace 0, 1 \rbrace$
• $A_1 = D_1$
• $B_N = C_{N-1} = C_N = 0$

Input

The input is given from Standard Input in the following format:

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$
$C_1$ $C_2$ $\dots$ $C_N$
$D_1$ $D_2$ $\dots$ $D_N$

Output

Print the number, modulo $998244353$, of walks of length $K$ starting at vertex $1$ and ending at vertex $N$.

Sample Input 1

3 3
1 0 1
1 1 0
1 0 0
1 0 1

Sample Output 1

6

The following figure shows the graph.

The following six walks satisfy the conditions.

• $1, 1, 1, 1, 3$
• $1, 1, 2, 3$
• $1, 1, 3, 3$
• $1, 2, 3, 3$
• $1, 3, 1, 3$
• $1, 3, 3, 3, 3$

Sample Input 2

4 6
1 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0

Sample Output 2

50

Sample Input 3

10 500000
0 1 0 1 0 0 0 0 1 1
1 1 1 0 1 1 1 0 1 0
0 0 1 1 0 0 1 1 0 0
0 1 1 1 1 1 0 1 1 0

Sample Output 3

866263864

问题描述

我们有一个有向图，包含$N$个顶点，编号为$1$到$N$。图中没有多边形，但可以有自环。同时，图中的每条边都满足以下条件。

• 如果边从顶点$s$到顶点$t$，那么$s$和$t$满足至少一个条件$0 \leq t - s\leq 2$和$t = 1$。

图中的边的存在或不存在由长度为$N$的序列$A, B, C, D$表示。$A, B, C, D$的每个元素具有以下含义。（设$A_n$表示$A$的第$n$个元素；$B_n, C_n, D_n$也是如此。）

• 如果从顶点$n$到顶点$n$有边，则$A_n$为$1$，否则为$0$。
• 如果从顶点$n$到顶点$n+1$有边，则$B_n$为$1$，否则为$0$。（这里，$B_N = 0$。）
• 如果从顶点$n$到顶点$n+2$有边，则$C_n$为$1$，否则为$0$。（这里，$C_{N-1} = C_N = 0$。）
• 如果从顶点$n$到顶点$1$有边，则$D_n$为$1$，否则为$0$。（这里，$D_1 = A_1$。）

在给定的图中，找到以顶点$1$为起点，以顶点$N$为终点，包含$K$条边的路径的数量（对$998244353$取模）。

这里，以顶点$1$为起点，以顶点$N$为终点，包含$K$条边的路径是一个顶点序列$v_0 = 1, v_1, \dots, v_K = N$，其中对于每个$i$ $(0 \leq i \lt K)$，从顶点$v_i$到顶点$v_{i + 1}$有边。当两个路径作为序列相同时，它们被认为是相同的。

限制条件

• $2 \leq N \leq 5 \times 10^4$
• $1 \leq K \leq 5 \times 10^5$
• $A_i, B_i, C_i, D_i \in \lbrace 0, 1 \rbrace$
• $A_1 = D_1$
• $B_N = C_{N-1} = C_N = 0$

输入

输入从标准输入以以下格式给出：

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$
$C_1$ $C_2$ $\dots$ $C_N$
$D_1$ $D_2$ $\dots$ $D_N$

输出

输出以顶点$1$为起点，以顶点$N$为终点，包含$K$条边的路径的数量（对$998244353$取模）。

样例输入1

3 3
1 0 1
1 1 0
1 0 0
1 0 1

样例输出1

6

下图显示了图。

满足条件的路径有以下六个。

• $1, 1, 1, 3$
• $1, 1, 2, 3$
• $1, 1, 3, 3$
• $1, 2, 3, 3$
• $1, 3, 1, 3$
• $1, 3, 3, 3$

样例输入2

4 6
1 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0

样例输出2

50

样例输入3

10 500000
0 1 0 1 0 0 0 0 1 1
1 1 1 0 1 1 1 0 1 0
0 0 1 1 0 0 1 1 0 0
0 1 1 1 1 1 0 1 1 0

样例输出3

866263864