No.2616 Median at the Middle Position
startcpp
p-adic
問題文最終更新日: 2023-12-21 22:21:48
English (AI translation)
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 416
(順位表)
の他の問題:
Problem Statement
You are given a permutation $P = (P_1, \cdots, P_N)$ of length $N$.
How many subsequences $p$ of $P$ satisfy all of the following conditions?
- The length is odd.
- The median of $p$ is located at the exact middle of $p$.
Input
$N$ $P_1$ $\cdots$ $P_N$
- All input values are integers.
- $1 \le N \le 300000$
- $(P_1, \cdots, P_N)$ is a permutation obtained by rearranging $(1, 2, \cdots, N)$.
Output
Output the answer modulo $998244353$.
Sample
Sample 1
Input
4 4 2 3 1
Output
6
The $6$ subsequences $(4), (2), (3), (1), (4, 2, 1), (4, 3, 1)$ satisfy the conditions.
Sample 2
Input
10 3 1 4 9 2 10 5 7 8 6
Output
98
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。