MCC 2025 P6: Increasing Subsequence Median Sum

Increasing Subsequence Median Sum

Statement

Evirir the dragon has a sequence of integers $A = [A_1, A_2, \ldots, A_N]$ and many definitions below.

A sequence $B$ is a subsequence of a sequence $A$ if $B$ can be obtained from $A$ by the deletion of several (possibly zero or all) elements from arbitrary positions. Two subsequences are considered different if the sets of positions of the deleted elements are different.

A subsequence $B = [B_1, B_2, \ldots, B_k]$ is strictly increasing if for all $i$ where $1 \leq i \leq k - 1$, $B_i < B_{i+1}$.

A subsequence $B = [B_1, B_2, \ldots, B_k]$ of $A$ is good if $B$ has odd length ($k$ is odd) and $B$ is strictly increasing.

The median of a good subsequence is the element in the middle of the subsequence. Formally, if $B = [B_1, B_2, ..., B_k]$ is a good subsequence, the median of $B$ is $B_{(k+1)/2}.$

Find the sum of the medians of all the good subsequences of $A$ modulo $998\,244\,353$.

Note: Modulo means “taking the remainder of”. For example, 15 modulo 6 is 3, 2 modulo 5 is 2, and 4 modulo 2 is 0. For this problem, you have to output the remainder of the answer after dividing by $998\,244\,353$.

Input Format

The first line contains a single integer $N$.

The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

Output Format

Output one integer, the sum of the medians of all good subsequences modulo $998\,244\,353$.

Constraints

For all tasks:

• $1 \leq N \leq 8000$.

• $1 \leq A_i \leq 10^9$ ($1 \le i \le N$).

• Task 1 (3 points): $A$ is strictly decreasing, i.e. $A_i > A_{i+1}$ for all $1 \le i < N$.
• Task 2 (5 points): $N \leq 20$
• Task 3 (8 points): $A_i \leq 3$ ($1 \le i \le N$)
• Task 4 (11 points): $A$ is strictly increasing, i.e. $A_i < A_{i+1}$ for all $1 \le i < N$.
• Task 5 (19 points): $N \leq 300$, $A_i \leq 300$ ($1 \le i \le N$)
• Task 6 (36 points): $A_i \leq 8000$ ($1 \le i \le N$)
• Task 7 (18 points): No additional constraints.

Sample Input

4
1 2 4 3

Sample Output

14

Sample Explanation

The sequence $A = [1,2,4,3]$ has six good subsequences:

• $B = [A_1] = [1]$ with median $1$.
• $B = [A_2] = [2]$ with median $2$.
• $B = [A_3] = [4]$ with median $4$.
• $B = [A_4] = [3]$ with median $3$.
• $B = [A_1, A_2, A_3] = [1,2,4]$ with median $2$.
• $B = [A_1, A_2, A_4] = [1,2,3]$ with median $2$.

Therefore, the answer is $1+2+4+3+2+2=14$.

The following are some examples of subsequences that are not good.

• $B = [A_4, A_3]$ because it is not a subsequence of $A$.
• $B = [A_1, A_2]$ because it is even length.
• $B = [A_1, A_3, A_4]$ because it is not strictly increasing.

Jumlah Median Subsekuens Meningkat (Increasing Subsequence Median Sum)

Pernyataan

Evirir si naga mempunyai satu jujukan integer $A = [A_1, A_2, \ldots, A_N]$ dan beberapa takrifan berikut.

Satu jujukan $B$ ialah subjujukan kepada jujukan $A$ jika $B$ boleh diperoleh daripada $A$ dengan memadamkan beberapa (mungkin sifar atau semua) elemen pada kedudukan yang sewenang-wenangnya. Dua subjujukan dianggap berbeza jika set bagi kedudukan bagi elemen yang dipadam adalah berbeza.

Subjujukan $B = [B_1, B_2, \ldots, B_k]$ dikatakan meningkat tegas (strictly increasing) jika bagi semua $i$ dengan $1 \leq i \leq k - 1$, $B_i < B_{i+1}$.

Subjujukan $B = [B_1, B_2, \ldots, B_k]$ bagi $A$ dipanggil baik jika panjang $B$ adalah ganjil ($k$ ganjil) dan $B$ meningkat tegas.

Median bagi subjujukan baik ialah elemen di tengah-tengah subjujukan. Secara formalnya, jika $B = [B_1, B_2, ..., B_k]$ ialah subjujukan baik, maka median $B$ ialah $B_{(k+1)/2}$.

Cari jumlah median bagi semua subsekuens baik A, modulo $998\,244\,353$.

Nota: Modulo bermaksud “ambil baki hasil bahagi”. Contohnya, 15 modulo 6 ialah 3, 2 modulo 5 ialah 2, dan 4 modulo 2 ialah 0. Dalam masalah ini, anda perlu keluarkan baki jawapan selepas dibahagi dengan $998\,244\,353$.

Format Input

Baris pertama mengandungi satu integer $N$. Baris kedua mengandungi $N$ integer yang dipisahkan oleh ruang: $A_1, A_2, \ldots, A_N$.

Format Output

Keluarkan satu integer, iaitu jumlah median semua subsekuens baik modulo $998\,244\,353$.

Kekangan

Untuk semua tugasan:

• $1 \leq N \leq 8000$.

• $1 \leq A_i \leq 10^9$ ($1 \le i \le N$).

• Tugasan 1 (3 markah): $A$ menurun tegas, iaitu $A_i > A_{i+1}$ untuk semua $1 \le i < N$.
• Tugasan 2 (5 markah): $N \leq 20$
• Tugasan 3 (8 markah): $A_i \leq 3$ ($1 \le i \le N$)
• Tugasan 4 (11 markah): $A$ meningkat tegas, iaitu $A_i < A_{i+1}$ untuk semua $1 \le i < N$.
• Tugasan 5 (19 markah): $N \leq 300$, $A_i \leq 300$ ($1 \le i \le N$)
• Tugasan 6 (36 markah): $A_i \leq 8000$ ($1 \le i \le N$)
• Tugasan 7 (18 markah): Tiada kekangan tambahan.

Contoh Input

4
1 2 4 3

Contoh Output

14

Penjelasan Contoh

Tatasusunan $A = [1,2,4,3]$ mempunyai enam subsekuens baik:

• $B = [A_1] = [1]$ dengan median $1$.
• $B = [A_2] = [2]$ dengan median $2$.
• $B = [A_3] = [4]$ dengan median $4$.
• $B = [A_4] = [3]$ dengan median $3$.
• $B = [A_1, A_2, A_3] = [1,2,4]$ dengan median $2$.
• $B = [A_1, A_2, A_4] = [1,2,3]$ dengan median $2$.

Oleh itu, jawapan ialah $1+2+4+3+2+2 = 14$.

Contoh subsekuens yang bukan baik:

• $B = [A_4, A_3]$ kerana ia bukan subsekuens $A$.
• $B = [A_1, A_2]$ kerana panjangnya genap.
• $B = [A_1, A_3, A_4]$ kerana tidak meningkat tegas.

递增子序列中位数之和

题目描述

龙 Evirir 有一个整数序列 $A = [A_1, A_2, \ldots, A_N]$，以及以下若干定义。

若序列 $B$ 可以通过从序列 $A$ 中删除若干个（可能为零个或全部）任意位置的元素得到，则称 $B$ 是 $A$ 的一个子序列。两个子序列被认为是不同的当且仅当被删除元素的位置集合不同。

若子序列 $B = [B_1, B_2, \ldots, B_k]$ 对所有 $1 \leq i \leq k - 1$，都满足 $B_i < B_{i+1}$，则称 $B$ 为一个严格递增子序列。

若子序列 $B = [B_1, B_2, \ldots, B_k]$ 的长度是奇数（即 $k$ 是奇数）且 $B$ 是严格递增子序列 则称 $B$ 为一个好子序列。

一个好子序列的中位数定义为该子序列中位于中间位置的元素。另一句话，若 $B = [B_1, B_2, \ldots, B_k]$ 是一个好子序列，则其中位数为 $B_{(k+1)/2}$。

求所有 $A$ 的好子序列的中位数之和，并将答案对 $998\,244\,353$ 取模。

注意：取模（modulo）表示“取余数”。例如，15 对 6 取模为 3，2 对 5 取模为 2，4 对 2 取模为 0。对于本题，请输出答案除以 $998\,244\,353$ 的余数。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个用空格分隔的整数 $A_1, A_2, \ldots, A_N$。

输出格式

输出一个整数——所有好子序列的中位数之和对 $998\,244\,353$ 取模后的结果

约束

对于每项任务：

• $1 \leq N \leq 8000$。

• $1 \leq A_i \leq 10^9$（$1 \le i \le N$）。

• 任务 1（3 分）：$A$ 是严格递减，即对所有 $1 \le i < N$，$A_i > A_{i+1}$。
• 任务 2（5 分）：$N \leq 20$
• 任务 3（8 分）：$A_i \leq 3$（$1 \le i \le N$）
• 任务 4（11 分）：$A$ 是严格递增，即对所有 $1 \le i < N$，$A_i < A_{i+1}$。
• 任务 5（19 分）：$N \leq 300$, $A_i \leq 300$（$1 \le i \le N$）
• 任务 6（36 分）：$A_i \leq 8000$（$1 \le i \le N$）
• 任务 7（18 分）：无额外约束

样例输入

4
1 2 4 3

样例输出

14

样例解释

序列 $A = [1,2,4,3]$ 有六个好子序列：

• $B = [A_1] = [1]$，其中位数是 $1$。
• $B = [A_2] = [2]$，其中位数是 $2$。
• $B = [A_3] = [4]$，其中位数是 $4$。
• $B = [A_4] = [3]$，其中位数是 $3$，
• $B = [A_1, A_2, A_3] = [1,2,4]$，其中位数是 $2$。
• $B = [A_1, A_2, A_4] = [1,2,3]$，其中位数是 $2$。

答案是 $1+2+4+3+2+2=14$。

以下是一些不好子序列的例子。

• $B = [A_4, A_3]$ 因为它不是 $A$ 的子序列。
• $B = [A_1, A_2]$ 因为它的长度是偶数。
• $B = [A_1, A_3, A_4]$ 因为他不是严格递增。