No.2250 Split Permutation
Problem Statement
You are given a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$. Consider generating a permutation $P'$ by performing the following operations on $P$ in order from top to bottom.
- Insert $0$ or more dividers into $P$ to split it into several non-empty contiguous subarrays, and call them $p_1,p_2,\ldots,p_k$ from left to right.
- Sort each of $p_1,p_2,\ldots,p_k$ in ascending order.
- Let $P'$ be the result of concatenating $p_1,p_2,\ldots,p_k$ from left to right in this order.
For example, when $P=(5,2,4,3,1)$, if $P$ is split into $(5,2),(4,3,1)$, sorting each in ascending order gives $(2,5),(1,3,4)$, so $P'=(2,5,1,3,4)$.
There are $2^{N-1}$ ways in total to split $P$. Find the sum of the inversion numbers of $P'$ over all of them, modulo $998244353$.
Input
$N$ $P_1\ P_2\ \ldots\ P_N$
- $1\le N\le 2×10^5$
- $1\le P_i\le N$
- If $i \neq j$, then $P_i \neq P_j$
- All input values are integers
Output
Output the answer.
Sample
Sample 1
Input
3 2 3 1
Output
5
When split as $(2,3,1)$, we get $P'=(1,2,3)$, whose inversion number is $0$.
When split as $(2,3),(1)$, we get $P'=(2,3,1)$, whose inversion number is $2$.
When split as $(2),(3,1)$, we get $P'=(2,1,3)$, whose inversion number is $1$.
When split as $(2),(3),(1)$, we get $P'=(2,3,1)$, whose inversion number is $2$.
Therefore, the answer is $0+2+1+2=5$.
Sample 2
Input
6 1 2 3 4 5 6
Output
0
No matter how it is split, the inversion number of $P'$ is $0$.
Sample 3
Input
9 2 9 6 5 4 1 7 8 3
Output
3838
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
bayashiko
ei1333333