問題一覧 > 通常問題

No.2327 Inversion Sum

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

問題文

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

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

入力

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

制約

  • $1 \leq N \leq 10 ^ 5$
  • $0 \leq M \leq N$
  • $1 \leq P_i, K_i \leq N$
  • $i \neq j$ ならば $P_i \neq P_j$ かつ $K_i \neq K_j$
  • 入力はすべて整数

出力

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

サンプル

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

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

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

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

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

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