問題一覧 > 通常問題

No.1321 Nurumeta

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 59
作問者 : polylogK / テスター : tsutaj
お気に入りにしたユーザー ProblemId : 5633 / 自分の提出
問題文最終更新日: 2021-01-08 23:46:46
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2020 (順位表) の他の問題:

Problem Statement

There are $N$ distinguishable balls, and initially each ball is colorless.

Kurumi-chan paints every ball with a color chosen from $M$ colors. She then considers the following problem for the $N$ painted balls.

  • When selecting $1$ or more balls from the $N$ balls, how many ways of selecting are there such that the number of distinct colors among the selected balls is exactly $K$?

Compute the answer to the above problem for every possible way of painting the balls, and output the sum of these answers. Since the answer can be very large, output it modulo $998244353$.

Input

$N\ M\ K$

  • $1 \le K \le M \le N \le 10^5$
  • All inputs are integers.

Output

Output the answer modulo $998244353$, followed by a newline.

Sample

Sample 1
Input
3 2 1
Output
38

Let the colors be represented by $0, 1$.

  • The answer for $[0, 0, 0]$ is $7$.
  • The answer for $[0, 0, 1]$ is $4$.
  • The answer for $[0, 1, 0]$ is $4$.
  • The answer for $[0, 1, 1]$ is $4$.
  • The answer for $[1, 0, 0]$ is $4$.
  • The answer for $[1, 0, 1]$ is $4$.
  • The answer for $[1, 1, 0]$ is $4$.
  • The answer for $[1, 1, 1]$ is $7$.
Therefore, the sum is $38$.

Sample 2
Input
2718 281 82
Output
712566806

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