問題一覧 > 通常問題

No.3096 Snake Path

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

問題文

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

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

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

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

入力

N KN\ K
  • 1≤N≤1031\leq N\leq 10^3
  • 0≤K≤2N−20\leq K\leq 2N-2
  • 入力はすべて整数

出力

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

サンプル

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

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

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

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