No.1970 ひよこ鑑定士
タグ : / 解いたユーザー数 12
作問者 : 57tggx / テスター : PCTprobability
問題文
ひよこ孵化場で,オスのひよこ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。