No.1325 Subsequence Score
タグ : / 解いたユーザー数 107
作問者 :
tsutaj
/ テスター :
_____TAB_____
monkukui2
問題文
長さ $N$ の整数列 $A = (a_1, a_2, \ldots, a_N)$ が与えられます。
$A$ からいくつかの要素を取り出し、元の順序を保ったまま並べることで数列 $B$ を作ることを考えます。より具体的には、$A$ から $i_1, i_2, \ldots, i_M$ 番目 ($1 \leq i_1 < i_2 < \cdots < i_M \leq N$) の要素を取り出し、$B = (b_1, b_2, \ldots, b_M) = (a_{i_1}, a_{i_2}, \ldots, a_{i_M})$ とすることを考えます。
長さ $M$ の数列 $B$ に対する スコア を、$\sum_{i=1}^{M} \left(i \times b_i \right)$ と定義します。$B$ が長さ $0$ の列である場合のスコアは $0$ です。
$B$ としてあり得るすべての数列に対してスコアを計算し、その総和を $998244353$ で割った余りを求めてください。なお、ふたつの数列 $(a_{i_1}, a_{i_2}, \ldots, a_{i_{M_1}})$, $(a_{j_1}, a_{j_2}, \ldots, a_{j_{M_2}})$ は、以下の条件のうち少なくとも一方を満たすときに区別されます。
- 長さが異なる。すなわち $M_1 \neq M_2$ である。
- 長さが等しく、添字列が異なる。すなわち $i_k \neq j_k$ となるような $k$ ($1 \leq k \leq M_1$) が存在する。
入力
$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$)
- 入力はすべて整数で与えられる
出力
答えを $998244353$ で割った余りを出力してください。最後に改行してください。
サンプル
サンプル1
入力
3 1 2 3
出力
40
数列 $B$ としてあり得るものは以下の $8$ 通りです。
| 数列 | スコア |
|---|---|
| $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$ |
スコアの合計は $40$ ですので、$40$ が答えです。
サンプル2
入力
10 3 1 4 1 5 9 2 6 5 3
出力
70656
最終的な数列が同一であっても、添字列が異なれば区別することに注意してください。
サンプル3
入力
20 107 308 203 269 817 203 123 593 200 252 753 198 200 201 987 222 687 354 901 734
出力
944766948
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。