No.2550 MORE! JUMP! MORE!
タグ : / 解いたユーザー数 47
作問者 :
dyktr_06
/ テスター :
sepa38
InTheBloom
Seed57_cash
ryota2357
Problem Statement
There is a staircase with $N$ steps. The lowest step is step $0$, and the number $A_i$ is written on step $i$.
You are on step $0$, and you repeat the following action until you jump to step $N$.
- In the $i$-th action, when you are on step $x$, choose an integer $j$ satisfying $x < j \leq N$. Then, gain a score of $i \times A_j$ and jump to step $j$.
Let $S$ be the total score you have gained by the time you jump to step $N$.
There are $2^{N - 1}$ possible sequences of actions until you jump to step $N$. Find the sum of $S$ over all of these sequences.
However, since the answer can be very large, find it modulo $998244353$.
Constraints
- $1 \leq N \leq 2 \times 10^{5}$
- $0 \leq A_i \leq 998244352$
- All inputs are integers.
Input
The input is given from standard input in the following format.
$N$ $A_1$ $A_2$ ... $A_N$
Output
Print the answer modulo $998244353$ on a single line.
Sample
Sample 1
Input
3 5 7 8
Output
95
The following $4$ sequences of actions are possible.
- Jump to step $3$. This gives $S = 1 \times 8 = 8$.
- Jump to steps $1, 3$ in this order. This gives $S = 1 \times 5 + 2 \times 8 = 21$.
- Jump to steps $2, 3$ in this order. This gives $S = 1 \times 7 + 2 \times 8 = 23$.
- Jump to steps $1, 2, 3$ in this order. This gives $S = 1 \times 5 + 2 \times 7 + 3 \times 8 = 43$.
Since $8 + 21 + 23 + 43 = 95$, print $95$.
Sample 2
Input
7 376873723 252623151 856139513 29843394 373100489 753241875 92750716
Output
686211551
Find the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。