問題一覧 > 通常問題

No.2544 Many RMQ Problems

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 52
作問者 : Shirotsume / テスター : 👑 AngrySadEight 👑 Nachia
お気に入りにしたユーザー ProblemId : 9939 / 自分の提出
問題文最終更新日: 2023-11-15 20:01:20
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
yukicoder contest 413 (順位表) の他の問題:

Problem Statement

Shirotsume found the following problem.

RMQ Problem

You are given a permutation $p$ obtained by rearranging $(1, 2, \dots, N)$. Process the following $Q$ queries.

  • Query $i$: Given a pair of integers $(L_i, R_i)$ satisfying $1 \leq L_i \leq R_i \leq N$, output the value of $\min(p_{L_i}, p_{L_i + 1}, \dots, p_{R_i})$.

Since this problem was a standard one for Shirotsume, he came up with the following problem.

Many RMQ Problems

You are given integers $N, Q$.

There are $\displaystyle N! \times \left ( \frac{N(N + 1)}{2} \right )^Q$ possible combinations of the values of $p$ and $L_i, R_i$ given in the input of RMQ Problem.

Find the sum of the values output when solving RMQ Problem for all of them, modulo $998244353$.

Solve Many RMQ Problems.

Constraints

  • All inputs are integers.
  • $1 \leq N, Q \leq 10^6$

Input

The input is given from standard input. The test case is given in the following format.

$N$ $Q$

Output

Output the answer.

Sample

Sample 1
Input
2 2
Output
48

There are $18$ possible inputs to RMQ Problem.

For example, for the input $p = (2, 1), (L_1, R_1) = (1, 2), (L_2, R_2) = (2, 2)$, the sum of the outputs is $\min(p_1, p_2) + \min(p_2) = 1 + 1 = 2$.

The sum of the answers over all possible inputs is $48$.

Sample 2
Input
3 3
Output
6264
Sample 3
Input
1 100
Output
100
Sample 4
Input
1000000 1000000
Output
519524455

Don't forget to find the remainder modulo $998244353$.

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