問題一覧 > 通常問題

No.1897 Sum of 2nd Max

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 : ShirotsumeShirotsume / テスター : miscalcmiscalc 👑 ygussanyygussany polylogKpolylogK
5 ProblemId : 7324 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-03 01:55:27

問題文

$1$ 以上 $K$ 以下の整数からなる長さ $N$ の数列は全部で $K^N$ 個あります。これらすべての数列に対する「降順に並べ替えたとき前から $2$ 番目になる要素」の総和を $998244353$ で割ったあまりを求めてください。

制約

  • 入力は全て整数
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq 2 \times 10^5$

入力

入力は以下の形式で標準入力から与えられる。 
$N$ $K$

出力

答えを出力せよ。 最後に改行すること。

サンプル

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

長さが $2$ で、すべての要素が $1$ 以上 $3$ 以下の整数である数列は全部で $9$ 個あります。それぞれについて、降順に並べ替えたとき $2$ 番目になる要素は以下の通りになります。

  • $(1, 1) \rightarrow 1$
  • $(1, 2) \rightarrow 1$
  • $(1, 3) \rightarrow 1$
  • $(2, 1) \rightarrow 1$
  • $(2, 2) \rightarrow 2$
  • $(2, 3) \rightarrow 2$
  • $(3, 1) \rightarrow 1$
  • $(3, 2) \rightarrow 2$
  • $(3, 3) \rightarrow 3$

よって、求める和は $1 + 1 + 1 + 1 + 2 + 2 + 1 + 2 + 3 = 14$ となります。

サンプル

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

長さが $3$ であり、すべての要素が $1$ 以上 $2$ 以下である数列は全部で $8$ 個あります。それぞれについて、降順に並べ替えたとき $2$ 番目になる要素は以下の通りになります。

  • $(1, 1, 1) \rightarrow 1$
  • $(1, 1, 2) \rightarrow 1$
  • $(1, 2, 1) \rightarrow 1$
  • $(1, 2, 2) \rightarrow 2$
  • $(2, 1, 1) \rightarrow 1$
  • $(2, 1, 2) \rightarrow 2$
  • $(2, 2, 1) \rightarrow 2$
  • $(2, 2, 2) \rightarrow 2$

よって、求める和は $1 + 1 + 1 + 2 + 1 + 2 + 2 + 2 = 12$ となります。

サンプル3
入力
9 5
出力
8768415

サンプル4
入力
200000 200000
出力
77687822

$998244353$ で割ったあまりを求めてください。

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