No.3096 Snake Path
問題文最終更新日: 2025-04-06 13:27:45
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Problem Statement
There is an undirected graph with $3N$ vertices, as shown below.

Specifically, it is the graph in which vertex $i$ and vertex $i+1$ are connected for each $1≦i≦3N-1$.
When you may additionally connect vertices that are adjacent in the figure (see below) at most $K$ times, find the number of possible simple paths from vertex $1$ to vertex $3N$, modulo $998244353$.
More formally
First, additionally connect adjacent vertices of the graph at most $K$ times. Then a path from vertex $1$ to vertex $3N$ can be represented as a sequence $S=(S_1, S_2, ..., S_M)$, where $S_i$ is the $i$-th vertex visited on the path and $M$ is the number of vertices visited on the path. Find the number of kinds of sequences that are possible.Here, two sequences are considered different if they have different numbers of elements, or if for some integer $i(1\leq i\leq M)$, the $i$-th element from the left $S_i$ differs between the $2$ sequences.
What adjacent means
For a vertex $i$, the quotient of $(i+2)$ divided by $3$ is defined as the column to which that vertex belongs. Suppose $2$ vertices are written in the $A, B$-th columns from the left, respectively, and the numbers written on them are $C, D$, respectively.- $|A-B|=1$
- $C+D≡1\ (mod6)$
Input
$N\ K$
- $1\leq N\leq 10^3$
- $0\leq K\leq 2N-2$
- All inputs are integers
Output
Find the number of possible simple paths, modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
2 1
Output
3
There are 3 simple paths, as shown below.
Sample 2
Input
314 159
Output
545088277
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamo21