問題一覧 > 通常問題

No.1325 Subsequence Score

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 83
作問者 : tsutajtsutaj / テスター : _____TAB__________TAB_____ monkukui2monkukui2
11 ProblemId : 3955 / 出題時の順位表
問題文最終更新日: 2021-01-08 23:47:15

問題文

長さ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。