No.1546 [Cherry 2nd Tune D] Not as Easy as You Might Think
Problem Statement
You are given a sequence of integers $A$. The first $T_1$ terms of this sequence are all $V_1$, the next $T_2$ terms are all $V_2$, $\dots$, and the last $T_N$ terms are all $V_N$.
Let $|A|$ denote the number of terms of $A$, and let $A_i$ be the $i$-th term of $A$.
For $L \leq R$, define
$\displaystyle \quad Y_{L,R}=1 \cdot A_L+2 \cdot A_{L+1}+\dots+(R-L+1)A_R=\sum_{k=L}^R (k-L+1) A_k$
and find
$\displaystyle \quad X=\sum_{L=1}^{|A|} \sum_{R=L}^{|A|} Y_{L,R}$
. However, since $X$ can be very large, output the remainder when $X$ is divided by $998244353$.
Constraints
- $1 \leq N \leq 3 \times 10^5$
- $1 \leq T_i \leq 10^{18}~(1 \leq i \leq N)$
- $0 \leq V_i < 998244353~(1 \leq i \leq N)$
- All input values are integers.
Input
$N$ $T_1$ $V_1$ $\vdots$ $T_N$ $V_N$
Output
Output the remainder when $X$ is divided by $998244353$. Do not forget the newline at the end.
Sample
Sample 1
Input
3 2 3 1 2 3 1
Output
192
We have $A=(3,3,2,1,1,1)$. Here, for example, $Y_{1,3}=1 \cdot 3+2 \cdot 3+ 3 \cdot 2=15$. Then, it can be seen that $X=192$.
Sample 2
Input
1 1 46
Output
46
We have $A=(46)$.
Sample 3
Input
11 173 141 205 421 80 356 756 237 887 309 100 504 629 504 352 880 744 168 634 872 150 420
Output
360323663
Note that you must output the remainder when divided by $998244353$. Also, it is possible that $V_i=V_{i+1}$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun