No.1100 Boxes
タグ : / 解いたユーザー数 64
作問者 :
SSRS
/ テスター :
37zigen
問題文
$N$個の互いに区別できるボールを、$K$個の互いに区別できる箱に入れます。
ただし、ボールが1つも入っていない箱の個数が奇数であるようにしたいです。
条件を満たすボールの入れ方は何通りあるか、求めてください。
答えは非常に大きくなることがあるので、$998244353$で割った余りを出力してください。
入力
$N \ K$
入力は以下の制約を満たします。
- 入力はすべて整数
- $1 \leq N \leq 10^7$
- $1 \leq K \leq 10^5$
出力
条件を満たすボールの入れ方の数を、$998244353$で割った余りを出力してください。
サンプル
サンプル1
入力
2 3
出力
6
ボールが2個、箱が3個あります。
2つのボールを同じ箱に入れると、ボールが1つも入っていない箱の個数は2個となり、条件を満たしません。
2つのボールを異なる箱に入れると、ボールが1つも入っていない箱の個数は1個となり、条件を満たします。
よって、答えは2つのボールを異なる箱に入れる入れ方の個数に等しく、6通りあります。
サンプル2
入力
4 1
出力
0
全てのボールを同じ箱に入れることになるので、どのように入れてもボールが1つも入っていない箱の個数は0個(偶数)になります。
サンプル3
入力
5 4
出力
604
サンプル4
入力
1000 100
出力
656749944
答えを$998244353$で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。