No.2130 分配方法の数え上げ mod 998244353
タグ : / 解いたユーザー数 115
作問者 : 👑
p-adic
/ テスター :
箱星
taiga0629kyopro
問題文
入力に正整数 $N$ と $M$ が与えられます。
トーラス大好きbotはご存知の通りドーナツが大好きなbotです。
トーラス大好きbot大好きbotはご存知の通りトーラス大好きbotが大好きなbotです。もちろん $2$ 体は別物です。
ある日、あなたはトーラス大好きbotとトーラス大好きbot大好きbotに合計 $N$ 種類のドーナツを $1$ 個ずつ買ってあげました。
この $N$ 種類のドーナツを $2$ 体に分配したいのですが、トーラス大好きbotはもらえる個数が $M$ 個以上でないと泣いてしまいます。
トーラス大好きbotが泣かないように $N$ 種類のドーナツを $2$ 体に分配する方法の総数を $998244353$ で割った余りを求めてください。
ただし分配する方法の総数を数える上で、異なる種類のドーナツは区別します。
入力
入力は次の形式で標準入力から与えられます：$N$ $M$
制約
入力は以下の制約を満たします：
- $N$ は $10^{18}$ 以下の正整数
- $M$ は $10^5$ 以下の正整数
出力
トーラス大好きbotが泣かないように $N$ 種類のドーナツを $2$ 体に分配する方法の総数を $998244353$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1
出力
1
あなたはドーナツを $1$ 種類 $1$ 個ずつ買ったので、トーラス大好きbotが泣かないようにトーラス大好きbotに $1$ 種類以上あげる分配方法は、
- あなたが買ってきた $1$ 個のドーナツをトーラス大好きbotにあげてトーラス大好きbot大好きbotにはあげないという分配方法
の $1$ 種類のみです。$1$ を $998244353$ で割った余りは $1$ です。
サンプル2
入力
1 2
出力
0
あなたはドーナツを $1$ 種類 $1$ 個ずつしか買わなかったので、トーラス大好きbotが泣かないようにトーラス大好きbotに $2$ 個以上あげる分配方法はありません。$0$ を $998244353$ で割った余りは $0$ です。
サンプル3
入力
2 1
出力
3
あなたはドーナツを $2$ 種類 $1$ 個ずつ買ったので、それらをドーナツAとドーナツBと置くと、トーラス大好きbotが泣かないようにトーラス大好きbotに $1$ 個以上あげる分配方法は、
- トーラス大好きbotにドーナツAをあげてトーラス大好きbot大好きbotにドーナツBをあげるという分配方法
- トーラス大好きbotにドーナツBをあげてトーラス大好きbot大好きbotにドーナツAをあげるという分配方法
- トーラス大好きbotにドーナツAとドーナツBをあげてトーラス大好きbot大好きbotにはドーナツをあげないという分配方法
の $3$ 種類です。$3$ を $998244353$ で割った余りは $3$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。