問題一覧 > 通常問題

No.2250 Split Permutation

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 94
作問者 : bayashiko / テスター : ei1333333 kumakuma
お気に入りにしたユーザー ProblemId : 9321 / 自分の提出
問題文最終更新日: 2023-03-13 14:19:17
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 381 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。