問題一覧 > 通常問題

No.3119 A Little Cheat

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : Nzt3 / テスター : ponjuice kenken714 Naru820
お気に入りにしたユーザー ProblemId : 12094 / 自分の提出
問題文最終更新日: 2025-04-18 00:29:11
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もしくは右上の雲マークをクリックしてアカウントを作成してください。