No.3119 A Little Cheat
問題文最終更新日: 2025-04-18 00:29:11
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
CPCTF 2025 : PPC
(順位表)
の他の問題:
Problem Statement
You are given a sequence $A$ of positive integers of length $N$. For an integer sequence $B$ of length $N$, the score $f(B)$ is defined as follows.
- Perform the following operation at most $1$ time.
- Choose an integer $i \ (1 \le i < N)$ and swap the values of $B_i$ and $B_{i+1}$.
- $f(B)$ is the maximum possible number of indices $i\ (1\le i \le N)$ satisfying $A_i < B_i$ when the operation is performed appropriately.
There are $M^N$ possible integer sequences $B$ of length $N$ whose elements are all between $1$ and $M$, inclusive. Find the score $f(B)$ for all of them, and output the sum of these scores modulo $998244353$.
Constraints
- $2 \le N \le 2 \times 10^5$
- $1 \le M \le 10^9$
- $1 \le A_i \le M\ (1 \le i \le N)$
- All input values are integers.
Input
The input is given from Standard Input in the following format.
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Output the answer.
Sample
Sample 1
Input
3 4 1 2 3
Output
117
There are $4^3 = 64$ possible sequences $B$.
By computing $f([1,1,1])=0,f([1,2,1])=1$ and so on, we find that the sum of the scores is $117$.
Sample 2
Input
9 10 9 9 8 2 4 4 3 5 3
Output
871841628
Sample 3
Input
10 100 82 28 26 33 15 28 21 56 32 48
Output
2025
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。