問題一覧 > 通常問題

No.1193 Penguin Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : penguinmanpenguinman / テスター : kaagekaage
2 ProblemId : 4849 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-17 05:30:21

問題文

Penguinmanは長さ N の数列 A を持っています。彼は今から次の操作を N 回行うことで、新しい数列 B を作ろうと思っています。初め数列 B は空です。

i 回目の操作 :
A から i 個の要素を選び、順番を変えずに B の末尾に追加する。

全ての要素の選び方における、数列 B の転倒数の総和を 998244353 で割った余りを求めてください。

ここである数列 C の転倒数とは、 i<j かつ Ci>Cj を満たす i,j(1i,j(Cの要素数)) の組の個数のことです。

入力

N
A1 A2 ... AN
  • 1N2×105
  • 1Ai109
  • 入力は全て整数

出力

答えを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

mod998244353 で出力することを忘れないでください。

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