問題一覧 > 通常問題

No.1970 ひよこ鑑定士

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : 57tggx57tggx / テスター : PCTprobabilityPCTprobability
3 ProblemId : 7910 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-04 13:10:59

問題文

ひよこ孵化場で,オスのひよこ $N$ 羽とメスのひよこ $N$ 羽が生まれました. 今から孵化場の人が $2N$ 羽全てのひよこを 1 列に並べます. ひよこ鑑定士であるあなたの仕事は, まず整数 $x$($1 \le x \le 2N$)を 1 つ決め, 次に 1 列に並んだひよこから連続した $x$ 羽を選び, そして選んだひよこを農家の人に売ることです.

しかし,あなたは選んだ $x$ 羽を全て売れるとは限りません. 孵化場の人は好きなオス 1 羽とメス 1 羽を選んでペアを作ることができ, あなたが選んだ $x$ 羽の中から できるだけ多くのペアを作って 連れ去ってしまいます. あなたが農家の人に売れるのは, 残ったひよこ(全てオスか全てメス)だけです.

あなたは農家の人から「性別は問わないが,$K$ 羽のひよこを売って欲しい」と言われています. 孵化場の人がひよこを 1 列に並べる並べ方は, 同じ性別のひよこを区別しない場合全部で $\binom{2N}{N}$ 通りありますが, そのうちあなたが整数 $x$ と連続した $x$ 羽のひよこをうまく選ぶことで 農家の人に $K$ 羽のひよこを売れるものは何通りありますか?

ただし,答えは非常に大きくなる可能性があるので, $998244353$ で割った余りを求めてください.

入力

$N\ K$
  • $N$,$K$ は整数.
  • $1 \le N \le 2 \times 10^5$
  • $1 \le K \le N$

出力

$\binom{2N}{N}$ 通りの並べ方のうち, 農家の人に $K$ 羽のひよこを売ることが可能な並べ方の数を $998244353$ で割った余りを出力し, 最後に改行してください。

サンプル

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

孵化場の人が「オス,メス,オス,メス」か「メス,オス,メス,オス」の順番に並べると, あなたが連続する $x$ 羽をどう選んでも,農家の人には最大で 1 羽しか売れません. 残りの 4 通りの並べ方であれば,連続する「オス,オス」か「メス,メス」を選ぶことで, 農家の人に 2 羽売ることができます.

サンプル2
入力
5 1
出力
252

孵化場の人がひよこをどう並べても, あなたが $x = 1$ とすればペアは作れません.

サンプル3
入力
100 80
出力
286724148

$998244353$ で割った余りを出力してください.

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