問題一覧 > 通常問題

No.1546 [Cherry 2nd Tune D] 思ったよりも易しくない

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 51
作問者 : KazunKazun / テスター : 👑 ningenMeningenMe
2 ProblemId : 6128 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-07 02:37:01

問題文

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