Yazid's Sequence

发布时间: 2018年9月30日 20:11   最后更新: 2018年11月29日 19:23   时间限制: 2000ms   内存限制: 256M

Yazid has a number sequence $A$ of length $n$, and now he wants to fill in a plus or multiplier between every two numbers to get an expression. Obviously, he has a total of $2 ^ {n - 1}$ different filling schemes. For each scheme, we specify its score as the value of the resulting expression.

The score of a sequence is the sum of all the filling scheme scores modulo $998,244,353$.

Yazid wants to know the score of the sequence. What's more, Yazid will make modification for several times, every time changing a number in the sequence, and you will need to tell him the score of the new sequence after each modification.

Read from standard input. The $1$st line contains one integer $n$. The $2$nd line contains $n$ space-seperated integers $A_1, \ldots, A_n$. The $3$rd line contains one integer $Q$. For the next $Q$ lines, each line contains two space-seperated integers $i, b$, representing a modification that changes $A_i$ to $b$.
$1 \le i \le n \le 2 \times 10 ^ 5$
$0 \le Q \le 2 \times 10 ^ 5$
$0 \le A_i , b < 998,244,353$

Write to the standard output.
Output $n + 1$ lines, $1$ integer per line. The $i$-th line is score of the sequence after the ($i - 1$)-th modification. In paticular, the $1$st line is the score of the initial sequence.

复制
3
1 2 3
2
1 4
2 1
24
54
34
复制
6
2 3 3 3 3 3
6
6 66
6 666
6 6666
2 33
2 333
2 3333
1934
25433
249233
2487233
18691463
180733763
802912410

The expressions for the $4$ schemes of the initial sequence are: $1 + 2 + 3 = 6$, $1 + 2 \times 3 = 7$, $1 \times 2 + 3 = 5$, $1 \times 2 \times 3 = 6$. So the sequence score is $6 + 7 + 5 + 6 = 24$.

After the $1$st modification, the new sequence is $4, 2, 3$.

After the $2$nd modification, the new sequence is $4, 1, 3$.


数据可能是假的,如果过不了请及时报警。

data structure

CCPC 2018 (Qinhuangdao)