No.1546 [Cherry 2nd Tune D] 思ったよりも易しくない
タグ : / 解いたユーザー数 55
作問者 :
Kazun
/ テスター :
ningenMe
問題文
整数の列 $A$ が与えられる. この列は最初の $T_1$ 項は全て $V_1$ , 続く $T_2$ 項は全て $V_2$ , $\dots$, 最後の $T_N$ 項は全て $V_N$ である.
$A$ の項の数を $|A|$ と表し, $A$ の第 $i$ 項を $A_i$ とする.
このとき, $L \leq R$ に対して,
$\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$
としたとき,
$\displaystyle \quad X=\sum_{L=1}^{|A|} \sum_{R=L}^{|A|} Y_{L,R}$
を求めよ. だだし, $X$ は非常に大きくなる可能性があるので, 出力の際には, $X$ を $998244353$ で割った余りを求めよ.
制約
- $1 \leq N \leq 3 \times 10^5$
- $1 \leq T_i \leq 10^{18}~(1 \leq i \leq N)$
- $0 \leq V_k < 998244353~(1 \leq i \leq N)$
- 入力は全て整数である.
入力
$N$ $T_1$ $V_1$ $\vdots$ $T_N$ $V_N$
出力
$X$ を $998244353$ で割った余りを出力せよ. 最後に改行を忘れないこと.
サンプル
サンプル1
入力
3 2 3 1 2 3 1
出力
192
$A=(3,3,2,1,1,1)$ である. このとき, 例えば, $Y_{1,3}=1 \cdot 3+2 \cdot 3+ 3 \cdot 2=15$ である. そして, $X=192$ となることがわかる.
サンプル2
入力
1 1 46
出力
46
$A=(46)$ である.
サンプル3
入力
11 173 141 205 421 80 356 756 237 887 309 100 504 629 504 352 880 744 168 634 872 150 420
出力
360323663
出力すべきは $998244353$ で割った余りであることに注意せよ. また, $V_i=V_{i+1}$ である可能性がある.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。