問題一覧 > 通常問題

No.3096 Snake Path

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : RiRinbaru / テスター : autumn09 downer hamo21 👑 ygussany Yotugi
3 ProblemId : 11827 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-06 13:27:45

問題文

以下のように、頂点数 $3N$ の無向グラフがあります。

具体的には、 $1≦i≦3N-1$ について、頂点 $i$ と 頂点 $i+1$ を結んだグラフです。
図中で隣り合う頂点(以下参照)を追加で高々 $K$ 回結べるとき、頂点 $1$ から頂点 $3N$ への単純パスとしてあり得る個数を $998244353$ で割った余りを求めてください。

より形式的には グラフに対して、まず隣り合う頂点を追加で高々 $K$ 回結びます。 すると頂点 $1$ から頂点 $3N$ へのパスを、そのパスにおいて $i$ 番目に通る頂点を $S_i$ 、そのパスにおいて通る頂点数を $M$ として、数列 $S=(S_1, S_2, ..., S_M)$ と表現できます。 このとき、その数列としてありうるものの種類を求めてください。
ただし数列は、要素数が異なるか、あるいはある整数 $i(1\leq i\leq M)$ について、左から $i$ 番目の要素 $S_i$ が $2$ つの数列で異なるとき、異なるとします。

隣り合うとは 頂点 $i$ について、$(i+2)$ を $3$ で割った商をその頂点の属する列と定義します。$2$ つの頂点がそれぞれ左から $A, B$ 列目に書かれており、またそこに書かれた数字をそれぞれ $C, D$ としたときに、
  • $|A-B|=1$
  • $C+D≡1\ (mod6)$
を満たすような頂点同士の関係のことです。

入力

$N\ K$
  • $1\leq N\leq 10^3$
  • $0\leq K\leq 2N-2$
  • 入力はすべて整数

出力

あり得る単純パスの個数を $998244353$ で割った余りを求めてください。 最後に改行してください。

サンプル

サンプル1
入力
2 1
出力
3

以下のように、単純パスは3つ存在します。

サンプル2
入力
314 159
出力
545088277

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。