問題一覧 > 通常問題

No.2327 Inversion Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 : sepa38 / テスター : phocom dyktr_06
3 ProblemId : 9608 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-24 08:38:08

問題文

(1,2,⋯ ,N)(1, 2, \cdots, N) の順列があります。 この順列は MM 個の制約を満たす必要があり、 ii 番目の制約は以下の通りです。

  • PiP_i は 前から KiK_i 番目に存在する
条件を満たす全ての順列について転倒数を求め、その和を出力してください。\\ ただし、答えは非常に大きくなる可能性があるため、  ⁣ ⁣ ⁣mod  998244353\! \! \! \mod 998244353 で出力してください。

入力

N MN\ M
P1 K1P_1\ K_1
P2 K2P_2\ K_2
    ⋮\ \ \ \ \vdots
PM KMP_M\ K_M

制約

  • 1≤N≤1051 \leq N \leq 10 ^ 5
  • 0≤M≤N0 \leq M \leq N
  • 1≤Pi,Ki≤N1 \leq P_i, K_i \leq N
  • i≠ji \neq j ならば Pi≠PjP_i \neq P_j かつ Ki≠KjK_i \neq K_j
  • 入力はすべて整数

出力

計算結果を 11 行に出力してください。

サンプル

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

条件を満たす順列は {2,1,3},{3,1,2}\{2, 1, 3\}, \{3, 1, 2\} の 22 つで、それぞれの転倒数は 1,21, 2 なので 1+2=31 + 2 = 3 を出力します。

サンプル2
入力
5 0
出力
600

サンプル3
入力
20 4
19 3
7 5
11 15
3 8
出力
936714253

 ⁣ ⁣ ⁣mod  998244353\! \! \! \mod 998244353 で出力することに注意してください。

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