問題一覧 > 通常問題

No.2327 Inversion Sum

レベル : / AI推定難易度 : 1875 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 67
作問者 : sepa38 / テスター : phocom dyktr_06
お気に入りにしたユーザー ProblemId : 9608 / 自分の提出
問題文最終更新日: 2023-05-24 08:38:08
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
MMA Contest 015 (順位表) の他の問題:

Problem Statement

Consider a permutation of $(1, 2, \cdots, N)$. This permutation must satisfy $M$ constraints, where the $i$-th constraint is as follows.

  • $P_i$ is located at the $K_i$-th position from the front
Find the inversion number of every permutation satisfying the conditions, and output their sum.$\\$ However, since the answer can be very large, output it $\! \! \! \mod 998244353$.

Input

$N\ M$
$P_1\ K_1$
$P_2\ K_2$
$\ \ \ \ \vdots$
$P_M\ K_M$

Constraints

  • $1 \leq N \leq 10 ^ 5$
  • $0 \leq M \leq N$
  • $1 \leq P_i, K_i \leq N$
  • If $i \neq j$, then $P_i \neq P_j$ and $K_i \neq K_j$
  • All input values are integers

Output

Output the result on $1$ line.

Sample

Sample 1
Input
3 1
1 2
Output
3

The permutations satisfying the conditions are the $2$ permutations $\{2, 1, 3\}, \{3, 1, 2\}$, whose inversion numbers are $1, 2$ respectively, so output $1 + 2 = 3$.

Sample 2
Input
5 0
Output
600

Sample 3
Input
20 4
19 3
7 5
11 15
3 8
Output
936714253

Note that the output must be given $\! \! \! \mod 998244353$.

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