問題一覧 > 通常問題

No.1193 Penguin Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 34
作問者 : penguinmanpenguinman / テスター : kaagekaage
1 ProblemId : 4849 / 出題時の順位表
問題文最終更新日: 2020-08-22 01:10:41

問題文

Penguinmanは長さ $N$ の数列 $A$ を持っています。Penguinmanは今から次の操作を $N$ 回行うことで、新しい数列 $B$ を作ろうと思っています。 初め数列 $B$ は空です。
$i$ 回目の操作:$A$ から $i$ 個の要素を選び、順番を変えずに $B$ の末尾に追加する。
全ての要素の選び方における、数列 $B$ の転倒数の総和を $998244353$ で割った余りを求めてください。
注:数列 $C$ の転倒数とは、 $i<j$ かつ $C_i>C_j$ を満たす $i, j(1≤i, j≤(C$の要素数$))$ の組の個数のことです。

入力

$N$
$A_1\ A_2\ ...\ A_N$

・$1≤N≤2×10^5$
・$1≤A_i≤10^9$
・入力は全て整数

出力

答えを1行に出力してください。

サンプル

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

最終的な数列 $B$ の状態は、{$1,1,2$}と{$2,1,2$}の$2$通りです。
転倒数はそれぞれ $0,1$ なので、それらの和である $1$ を出力します。

サンプル2
入力
4
4 1 2 2
出力
1530

数列 $A$ の各要素の値が相異なるとは限らないことに注意してください。

サンプル3
入力
8
1 43 2 5 92 10 91 100
出力
258159887

$\bmod 998244353$ で出力することを忘れないでください。

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