J - Sum Sum
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
正整数 N, M および、長さ N の正整数列 a, b が与えられます。 \sum\limits_{k=1}^N \sum\limits_{x=1}^M (a_k x^k + b_k k^x) を 998244353 で割った余りを求めてください。
制約
- 1 \leq N \leq 200{,}000
- 1 \leq M \leq 10^{18}
- 1 \leq a_k \leq 10^{9}
- 1 \leq b_k \leq 10^{9}
- 入力はすべて整数
小課題
- (1 点) N \leq 100
- (1 点) N \leq 5{,}000
- (98 点) 追加の制約はない
入力
入力は以下の形式で標準入力から与えられます。
N M a_1 a_2 \dots a_N b_1 b_2 \dots b_N
出力
答えを出力してください。
入力例 1
3 2 2 1 7 5 4 2
出力例 1
132
答えは (2 \times 1^1+5 \times 1^1) + (2 \times 2^1+5 \times 1^2) + (1 \times 1^2+4 \times 2^1) + (1 \times 2^2+4 \times 2^2) + (7 \times 1^3+2 \times 3^1) + (7 \times 2^3+2 \times 3^2) = 132 です。
このテストケースは小課題 1, 2 の制約を満たします。
入力例 2
5 123456789012345678 180484765 48450102 509940465 587404308 566608826 261439033 751569102 489070200 768834397 292361745
出力例 2
449755530
このテストケースは小課題 1, 2 の制約を満たします。