No.3826 PRiSM Net
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 :
Rho
/ テスター :
259-Momone
shiomusubi496
okkuu
タグ : / 解いたユーザー数 11
作問者 :
Rho
/ テスター :
shiomusubi496
問題文最終更新日: 2026-11-22 10:55:34
TSG LIVE! 17 プログラミングコンテスト
(順位表)
の他の問題:
問題文
全ての面が区別可能な正 $N$ 角柱があります。この角柱は上面、下面および 側面 $1$, 側面 $2, \dots, $ 側面 $N$ から成ります。 この角柱をいくつかの辺に沿って切り開くことで、連結な展開図を作成します。 展開図の面どうしが重なりを持っても構いません。
角柱の切り開き方であって、上面に直接接続する側面が $K$ 枚かつ下面に直接接続する側面が $L$ 枚であるようなものの通り数を $998244353$ で割った余りを求めてください。 より厳密には、角柱の辺を赤と青の $2$ 色で塗り分ける方法のうち以下の条件を満たす通り数を求めてください。
- 角柱のどの $2$ 頂点も赤の辺をたどって行き来できる
- 角柱のどの $2$ 面も青の辺をまたいで行き来できる
- 上面を囲む $N$ 本の辺のうち、青い辺はちょうど $K$ 本
- 下面を囲む $N$ 本の辺のうち、青い辺はちょうど $L$ 本
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- $1 \le T \le 10^4$
- $3 \le N \le 10^6$
- $1 \le K,L \le N$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$N\ K\ L$
出力
$T$ 行出力せよ。 $i$ 行目 $(1 \le i \le T)$ には、 $i$ 番目のテストケースに対する答えを出力せよ。
サンプル
サンプル1
入力
4 4 4 1 4 2 2 5 3 5 200000 50000 60000
出力
4 64 0 564730041
$1,2$ 番目のケースはともに四角柱を表しています。
$1$ 番目のケースにおいて、上面に $4$ 枚、下面に $1$ 枚の側面が接続する切り開き方は以下の4通りです。
$2$ 番目のケースにおいて、上面に $2$ 枚、下面に $2$ 枚の側面が接続する切り開き方は全部で $64$ 通りあります。 そのうちの一つを例として示します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。