No.1193 Penguin Sequence
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 :
penguinman
/ テスター :
kaage
タグ : / 解いたユーザー数 47
作問者 :
penguinman
/ テスター :
kaage
問題文最終更新日: 2021-01-17 05:30:21
問題文
Penguinmanは長さ $N$ の数列 $A$ を持っています。彼は今から次の操作を $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もしくは右上の雲マークをクリックしてアカウントを作成してください。