← 返回题目列表

AtCoder · abc438_g

G. 最小值总和

中文机器翻译题面 查看原题

分数: 575 点

问题陈述

给你整数 N,M,K,长度-N 整数序列 A=(A_0,A_1,\ldots,A_{N-1}),以及长度-M 整数序列 B=(B_0,B_1,\ldots,B_{M-1})。请注意,索引从 0.

查找 每对 \displaystyle\sum_{i=0}^{K-1} \min(A_{i\bmod N}, B_{i \bmod M}) ,模数 998244353.

约束

  • 1\le N,M\le 2\times 10^5
  • 1\le K\le 10^{18}
  • 1\le A_i,B_i\le 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M K
A_0 A_1 \ldots A_{N-1}
B_0 B_1 \ldots B_{M-1}

输出

输出 \displaystyle\sum_{i=0}^{K-1} \min(A_{i\bmod N}, B_{i \bmod M}) ,模数 998244353.


示例输入 1

3 2 5
3 1 4
1 5

示例输出 1

7

所需值为 \min(3,1)+\min(1,5)+\min(4,1)+\min(3,5)+\min(1,1)=7.


示例输入 2

4 4 27
6 1 10 42
87 6 21 33

示例输出 2

317

示例输入 3

5 7 583272014892537201
763832259 547096173 408327452 685495693 212251318
850800766 845647066 240229336 648345577 691868483 740301913 740485849

示例输出 3

931208848

计算模数 998244353.