l255. C - 很多區間最小值總和問題 - 高中生程式解題系統

內容

區間最小值總和問題

給你一個長度為 $N$ 的正整數數列 $(A_{1}, A_{2}, A_{3}, . . ., A_{N})$ ，定義 $MIN(S)$ 代表一個集合 $S$ 裡面最小的那個值，例如 : $MIN (1, 3, 4) = 1$ ，想請你求所有數對 $(l, r)$ 符合 $1 \leq l \leq r \leq N$ 的 $MIN (A_{l}, A_{l + 1}, . . ., A_{r})$ 的總和，也就是請你求以下的東西 :

$\sum_{l = 1}^{N} \sum_{r = l}^{N} MIN (A_{l}, A_{l + 1}, . . ., A_{r})$

以上是 r1cky 想到的問題，但他覺得有點太簡單，所以他把它改成了以下的題目 :

很多區間最小值總和問題

給予兩個正整數 $N, M$ ，代表所有長度為 $N$ 的正整數數列 $(A_{1}, A_{2}, A_{3}, . . ., A_{N})$ 符合 $1 \leq A_{i} \leq M (1 \leq i \leq N)$ ，總共有 $M^{N}$ 個滿足此條件且相異的數列，請你求這 $M^{N}$ 個數列對於 區間最小值總和問題 的答案總和，因為答案可能很大，請模 $998244353$ 。

解決 很多區間最小值總和問題 。

輸入說明

輸入有一行，代表兩個正整數 $N, M$ ，中間以空格隔開。

$1 \leq N, M \leq 2 \times 10^{5}$

輸出說明

輸出答案模 $998244353$ 。

範例輸入 #1

2 2

範例輸出 #1

範例輸入 #2

20 10

範例輸出 #2

982045350

範例輸入 #3

31415 48763

範例輸出 #3

502635375

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 2.0s , <1K
不公開測資點#1 (5%): 2.0s , <1K
不公開測資點#2 (5%): 2.0s , <1K
不公開測資點#3 (5%): 2.0s , <1K
不公開測資點#4 (5%): 2.0s , <1K
不公開測資點#5 (5%): 2.0s , <1K
不公開測資點#6 (5%): 2.0s , <1K
不公開測資點#7 (5%): 2.0s , <1K
不公開測資點#8 (5%): 2.0s , <1K
不公開測資點#9 (5%): 2.0s , <1K
不公開測資點#10 (5%): 2.0s , <1K
不公開測資點#11 (5%): 2.0s , <1K
不公開測資點#12 (5%): 2.0s , <1K
不公開測資點#13 (5%): 2.0s , <1K
不公開測資點#14 (5%): 2.0s , <1K
不公開測資點#15 (5%): 2.0s , <1K
不公開測資點#16 (5%): 2.0s , <1K
不公開測資點#17 (5%): 2.0s , <1K
不公開測資點#18 (5%): 2.0s , <1K
不公開測資點#19 (5%): 2.0s , <1K

提示：

範例輸入 # 1

以下為了方便解釋，我們定義 $F (X)$ 代表序列 $X$ 對於 區間最小值總和問題 的答案，並且我們對於每個可能的序列進行以下分析 :

當 $(N, M) = (2, 2)$ 時，序列有可能是 $(1, 1), (1, 2), (2, 1), (2, 2)$ 這 $4$ 種。

$A = (1, 1)$ ， $F (A) = MIN (1) + MIN (1) + MIN (1, 1) = 1 + 1 + 1 = 3$ 。

$A = (1, 2)$ ， $F (A) = MIN (1) + MIN (2) + MIN (1, 1) = 1 + 2 + 1 = 4$ 。

$A = (2, 1)$ ， $F (A) = MIN (2) + MIN (1) + MIN (2, 1) = 2 + 1 + 1 = 4$ 。

$A = (2, 2)$ ， $F (A) = MIN (2) + MIN (2) + MIN (2, 2) = 2 + 2 + 2 = 6$ 。

所以 $\sum F (A) = 3 + 4 + 4 + 6 = 17$ ，答案為 $17$ 。

範例輸入 # 2 & 3

請記得將答案模 $998244353$ 。

Authored by r1cky

標籤:

出處:

第一屆Chi怪壓常比賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
36778	r1cky (hehe)	l255		322	2023-08-08 10:10