問題一覧 > 通常問題

No.1100 Boxes

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 41
作問者 : SSRSSSRS / テスター : 37zigen37zigen
5 ProblemId : 4373 / 出題時の順位表
問題文最終更新日: 2020-06-26 08:14:01

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。