No.1325 Subsequence Score
タグ : / 解いたユーザー数 114
作問者 :
tsutaj
/ テスター :
_____TAB_____
monkukui2
Problem Statement
You are given an integer sequence $A = (a_1, a_2, \ldots, a_N)$ of length $N$.
Consider creating a sequence $B$ by taking some elements from $A$ and arranging them while preserving their original order. More specifically, consider taking the $i_1, i_2, \ldots, i_M$-th elements ($1 \leq i_1 < i_2 < \cdots < i_M \leq N$) from $A$ and letting $B = (b_1, b_2, \ldots, b_M) = (a_{i_1}, a_{i_2}, \ldots, a_{i_M})$.
The score of a sequence $B$ of length $M$ is defined as $\sum_{i=1}^{M} \left(i \times b_i \right)$. If $B$ is a sequence of length $0$, its score is $0$.
Calculate the score for every possible sequence $B$, and find the sum of these scores modulo $998244353$. Two sequences $(a_{i_1}, a_{i_2}, \ldots, a_{i_{M_1}})$ and $(a_{j_1}, a_{j_2}, \ldots, a_{j_{M_2}})$ are distinguished when at least one of the following conditions is satisfied.
- Their lengths differ, that is, $M_1 \neq M_2$.
- Their lengths are equal and their index sequences differ, that is, there exists $k$ ($1 \leq k \leq M_1$) such that $i_k \neq j_k$.
Input
$N$ $a_1$ $a_2$ $\ldots$ $a_N$
- $1 \leq N \leq 500,000$
- $1 \leq a_i \leq 10^9$ ($1 \leq i \leq N$)
- All input values are integers.
Output
Output the answer modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
3 1 2 3
Output
40
The following $8$ sequences are possible as $B$.
| Sequence | Score |
|---|---|
| $B = ()$ | $0$ |
| $B = (1)$ | $1 \times 1 = 1$ |
| $B = (1, 2)$ | $1 \times 1 + 2 \times 2 = 5$ |
| $B = (1, 2, 3)$ | $1 \times 1 + 2 \times 2 + 3 \times 3 = 14$ |
| $B = (1, 3)$ | $1 \times 1 + 2 \times 3 = 7$ |
| $B = (2)$ | $1 \times 2 = 2$ |
| $B = (2, 3)$ | $1 \times 2 + 2 \times 3 = 8$ |
| $B = (3)$ | $1 \times 3 = 3$ |
The total of the scores is $40$, so $40$ is the answer.
Sample 2
Input
10 3 1 4 1 5 9 2 6 5 3
Output
70656
Note that even if the resulting sequences are identical, they are distinguished if their index sequences differ.
Sample 3
Input
20 107 308 203 269 817 203 123 593 200 252 753 198 200 201 987 222 687 354 901 734
Output
944766948
Output the remainder modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。