問題一覧 > 通常問題

No.2544 Many RMQ Problems

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : ShirotsumeShirotsume / テスター : 👑 AngrySadEightAngrySadEight 👑 NachiaNachia
2 ProblemId : 9939 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-15 20:01:20

問題文

Shirotsume くんは以下の問題を見つけました。

RMQ Problem

$(1, 2, \dots, N)$ を並べ替えてできる順列 $p$ が与えられます。次の $Q$ 個のクエリを処理してください。

  • クエリ $i$ : $1 \leq L_i \leq R_i \leq N$ を満たす整数の組 $(L_i, R_i)$ が与えられるので、$\min(p_{L_i}, p_{L_i + 1}, \dots, p_{R_i})$ の値を出力してください。

Shirotsume くんにとってこの問題は典型だったので、以下の問題を考えました。

Many RMQ Problems

整数 $N, Q$ が与えられます。

RMQ Problem の入力で与えられる $p$ および $L_i, R_i$ の値の組合せは全部で $\displaystyle N! \times \left ( \frac{N(N + 1)}{2} \right )^Q$ 通りあります。

それらすべてに対して RMQ Problem を解いたときに出力される値の総和を $998244353$ で割った余りを求めてください。

Many RMQ Problems を解いてください。

制約

  • 入力はすべて整数
  • $1 \leq N, Q \leq 10^6$

入力

入力は標準入力から与えられる。テストケースは以下の形式で与えられる。

$N$ $Q$

出力

答えを出力せよ。

サンプル

サンプル1
入力
2 2
出力
48

RMQ Problem の入力としてありうるものは $18$ 通りあります。

例えば、$p = (2, 1), (L_1, R_1) = (1, 2), (L_2, R_2) = (2, 2)$ という入力に対し、出力の和は $\min(p_1, p_2) + \min(p_2) = 1 + 1 = 2$ となります。

ありうる入力すべてに対する答えの総和は $48$ となります。

サンプル2
入力
3 3
出力
6264
サンプル3
入力
1 100
出力
100
サンプル4
入力
1000000 1000000
出力
519524455

$998244353$ で割った余りを求めることを忘れずに。

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