No.1193 Penguin Sequence
タグ : / 解いたユーザー数 48
作問者 :
penguinman
/ テスター :
kaage
Problem Statement
Penguinman has a sequence $A$ of length $N$. He is going to create a new sequence $B$ by performing the following operation $N$ times. Initially, the sequence $B$ is empty.
- The $i$-th operation:
- Choose $i$ elements from $A$ and append them to the end of $B$ without changing their order.
Find the sum of the inversion numbers of the sequence $B$ over all ways of choosing the elements, modulo $998244353$.
Here, the inversion number of a sequence $C$ is the number of pairs $i, j(1≤i, j≤(C$'s number of elements$))$ satisfying $i<j$ and $C_i>C_j$.
Input
$N$ $A_1\ A_2\ ...\ A_N$
- $1≤N≤2×10^5$
- $1≤A_i≤10^9$
- All inputs are integers.
Output
Print the answer on 1 line.
Sample
Sample 1
Input
2 1 2
Output
1
There are $2$ possible final states of the sequence $B$: {$1,1,2$} and {$2,1,2$}.
Their inversion numbers are $0,1$ respectively, so print their sum, $1$.
Sample 2
Input
4 4 1 2 2
Output
1530
Note that the elements of the sequence $A$ are not necessarily distinct.
Sample 3
Input
8 1 43 2 5 92 10 91 100
Output
258159887
Do not forget to print the answer $\bmod 998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。