[AGC021E] Ball Eat Chameleons
题意翻译
有 $n$ 只变色龙,一开始都是蓝色。现在你喂了 $k$ 次球,每次指定一只变色龙吃下你指定颜色的球。
一只变色龙从蓝色变成红色当且仅当它吃的红球比蓝球多;
一只变色龙从红色变成蓝色当且仅当它吃的蓝球比红球多。
求最后能使所有变色龙都变成红色的方案数。
两个方案不同当且仅当至少一次喂的球颜色不同(**而不是喂的变色龙不同**)。
**注意:存在一次喂的变色龙不同的两个方案可能是相同的方案。**
题目描述
[problemUrl]: https://atcoder.jp/contests/agc021/tasks/agc021_e
AtCoder 共和国では、カメレオン科ボールタベルカメレオン属に属するスヌケカメレオンがペットとして大人気です。 りんごさんは、$ N $ 匹のスヌケカメレオンの個体をひとつのカゴに入れて飼っています。
何も食べていない状態のスヌケカメレオンは青色です。スヌケカメレオンは、次の規則で変色します。
- 青いスヌケカメレオンは、これまでに食べた青いボールの個数よりこれまでに食べた赤いボールの個数の方が真に大きくなった時、赤色に変色する。
- 赤いスヌケカメレオンは、これまでに食べた赤いボールの個数よりこれまでに食べた青いボールの個数の方が真に大きくなった時、青色に変色する。
最初、スヌケカメレオンたちはどの個体も何も食べていない状態です。りんごさんは、スヌケカメレオンたちに、以下の手順を $ K $ 回繰り返すことで餌をやりました。
- 赤いボールまたは青いボールを握る。
- 握ったボールを、スヌケカメレオンたちの入ったカゴの中に投げ入れる。このとき、いずれか一匹がそのボールを食べる。
りんごさんが $ K $ 個のボールを投げ入れたところ、全ての個体が赤色になっていました。りんごさんの $ K $ 個のボールの投げ入れ方としてありうるものは何通りあるでしょうか。 $ 998244353 $ で割った余りを求めてください。ただし、$ 2 $ つの投げ入れ方が異なるとは、ある $ i $ が存在し、$ i $ 個目に投げ入れたボールの色が異なることを指します。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ K $
输出格式
$ K $ 個のボールの投げ入れ方としてありうるものの個数を $ 998244353 $ で割った余りを出力せよ。
输入输出样例
输入样例 #1
2 4
输出样例 #1
7
输入样例 #2
3 7
输出样例 #2
57
输入样例 #3
8 3
输出样例 #3
0
输入样例 #4
8 10
输出样例 #4
46
输入样例 #5
123456 234567
输出样例 #5
857617983
说明
### 制約
- $ 1\ \leq\ N,K\ \leq\ 5\ \times\ 10^5 $
- $ N,K $ は整数である
### Sample Explanation 1
$ i $ 個目に投げ入れるボールが赤のとき `R` を、青のとき `B` を順に並べた文字列を用いて投げ入れ方を表せば、 `BRRR`,`RBRB`,`RBRR`,`RRBB`,`RRBR`,`RRRB`,`RRRR` の $ 7 $ 個が条件を満たします。