問題一覧 > 教育的問題

No.2130 分配方法の数え上げ mod 998244353

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 115
作問者 : 👑 p-adic / テスター : 箱星 taiga0629kyopro
0 ProblemId : 8616 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-08 00:27:13

問題文

入力に正整数 NN と MM が与えられます。

　

トーラス大好きbotはご存知の通りドーナツが大好きなbotです。

トーラス大好きbot大好きbotはご存知の通りトーラス大好きbotが大好きなbotです。もちろん 22 体は別物です。

ある日、あなたはトーラス大好きbotとトーラス大好きbot大好きbotに合計 NN 種類のドーナツを 11 個ずつ買ってあげました。

この NN 種類のドーナツを 22 体に分配したいのですが、トーラス大好きbotはもらえる個数が MM 個以上でないと泣いてしまいます。

　

トーラス大好きbotが泣かないように NN 種類のドーナツを 22 体に分配する方法の総数を 998244353998244353 で割った余りを求めてください。

ただし分配する方法の総数を数える上で、異なる種類のドーナツは区別します。

入力

入力は次の形式で標準入力から与えられます： 
NN
MM

制約

入力は以下の制約を満たします：

  • NN は 101810^{18} 以下の正整数
  • MM は 10510^5 以下の正整数

出力

トーラス大好きbotが泣かないように NN 種類のドーナツを 22 体に分配する方法の総数を 998244353998244353 で割った余りを出力してください。

最後に改行してください。

サンプル

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

あなたはドーナツを 11 種類 11 個ずつ買ったので、トーラス大好きbotが泣かないようにトーラス大好きbotに 11 種類以上あげる分配方法は、

  • あなたが買ってきた 11 個のドーナツをトーラス大好きbotにあげてトーラス大好きbot大好きbotにはあげないという分配方法

の 11 種類のみです。11 を 998244353998244353 で割った余りは 11 です。

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

あなたはドーナツを 11 種類 11 個ずつしか買わなかったので、トーラス大好きbotが泣かないようにトーラス大好きbotに 22 個以上あげる分配方法はありません。00 を 998244353998244353 で割った余りは 00 です。

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

あなたはドーナツを 22 種類 11 個ずつ買ったので、それらをドーナツAとドーナツBと置くと、トーラス大好きbotが泣かないようにトーラス大好きbotに 11 個以上あげる分配方法は、

  • トーラス大好きbotにドーナツAをあげてトーラス大好きbot大好きbotにドーナツBをあげるという分配方法
  • トーラス大好きbotにドーナツBをあげてトーラス大好きbot大好きbotにドーナツAをあげるという分配方法
  • トーラス大好きbotにドーナツAとドーナツBをあげてトーラス大好きbot大好きbotにはドーナツをあげないという分配方法

の 33 種類です。33 を 998244353998244353 で割った余りは 33 です。

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