C. 部分排序 · AC 题库

第 228 场 AtCoder Regular Contest++

部分排序

Partially Sort

AtCoder

⌀ 2953

原题

← BD →

部分排序AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$ .

给定一个 $(1,2,\dots,N)$ 的排列 $P=(P_1,P_2,\dots,P_N)$ 。AI (CI翻译)

For a subsequence $x=(x_1,x_2,\dots,x_k)$ of $(1,2,\dots,N)$ , let $f(x)$ denote the sequence obtained by the following procedure.

对于 $(1,2,\dots,N)$ 的一个子序列 $x=(x_1,x_2,\dots,x_k)$ ，定义 $f(x)$ 为按照以下步骤得到的序列。AI (CI翻译)

Initialize the sequence $Q=(Q_1,Q_2,\dots,Q_N)$ with $Q = P$ .
Let $A=(A_1,A_2,\dots,A_k)$ be the sequence obtained by sorting $(Q_{x_1},Q_{x_2},\dots,Q_{x_k})$ in ascending order.
For every integer $i$ satisfying $1 \le i \le k$ , replace $Q_{x_i}$ with $A_i$ . Let $f(x)$ be $Q$ at this point.

将序列 $Q=(Q_1,Q_2,\dots,Q_N)$ 初始化为 $Q = P$ 。
将 $(Q_{x_1},Q_{x_2},\dots,Q_{x_k})$ 按升序排序，得到序列 $A=(A_1,A_2,\dots,A_k)$ 。
对于满足 $1 \le i \le k$ 的每个整数 $i$ ，将 $Q_{x_i}$ 替换为 $A_i$ 。此时的 $Q$ 即为 $f(x)$ 。

AI (CI翻译)

There are $2^N$ possible choices of $x$ , including the empty sequence. Find the sum, modulo $998244353$ , of the number of inversions of $f(x)$ over all those choices.

共有 $2^N$ 种 $x$ 的选择方式，其中包括空序列。求所有这些选择对应的 $f(x)$ 的逆序对数之和，结果对 $998244353$ 取模。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$2 \le N \le 2 \times 10^5$
$P$ is a permutation of $(1,2,\dots,N)$ .
All input values are integers.

$2 \le N \le 2 \times 10^5$
$P$ 是 $(1,2,\dots,N)$ 的一个排列。
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N
P_1\ P_2\ \dots\ P_N

N
P_1\ P_2\ \dots\ P_N

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer.

输出答案。AI (CI翻译)

样例

Input #1

3
3 1 2

Output #1

$f(x)$ and its number of inversions for all eight possible choices of $x$ are as follows. - For $x = ()$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$. - For $x = (1)$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$. - For $x = (2)$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$. - For $x = (3)$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$. - For $x = (1,2)$, we have $f(x) = (1,3,2)$, and the number of inversions is $1$. - For $x = (1,3)$, we have $f(x) = (2,1,3)$, and the number of inversions is $1$. - For $x = (2,3)$, we have $f(x) = (3,1,2)$, and the number of inversions is $2$. - For $x = (1,2,3)$, we have $f(x) = (1,2,3)$, and the number of inversions is $0$. Thus, the answer is $2+2+2+2+1+1+2+0=12$.

Input #2

5
4 2 5 3 1

Output #2

Input #3

13
2 7 4 9 3 13 8 12 6 5 10 11 1

Output #3

题目信息

题号

arc228_c

所属比赛

第 228 场 AtCoder Regular Contest++

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。