問題一覧 > 通常問題

No.3096 Snake Path

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : RiRinbaru / テスター : autumn09 downer hamo21 ygussany Yotugi
お気に入りにしたユーザー ProblemId : 11827 / 自分の提出
問題文最終更新日: 2025-04-06 13:27:45
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
QUPC2024 (順位表) の他の問題:

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)$
Adjacent refers to the relation between vertices that satisfy the conditions above.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。