分数: 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.