/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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 で割ったあまりを求めてください。
Score : 575 points
Problem Statement
You are given integers N,M,K, a length-N integer sequence A=(A_0,A_1,\ldots,A_{N-1}), and a length-M integer sequence B=(B_0,B_1,\ldots,B_{M-1}). Note that the indices start from 0.
Find \displaystyle\sum_{i=0}^{K-1} \min(A_{i\bmod N}, B_{i \bmod M}) , modulo 998244353.
Constraints
- 1\le N,M\le 2\times 10^5
- 1\le K\le 10^{18}
- 1\le A_i,B_i\le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K
A_0 A_1 \ldots A_{N-1}
B_0 B_1 \ldots B_{M-1}
Output
Output \displaystyle\sum_{i=0}^{K-1} \min(A_{i\bmod N}, B_{i \bmod M}) , modulo 998244353.
Sample Input 1
3 2 5 3 1 4 1 5
Sample Output 1
7
The desired value is \min(3,1)+\min(1,5)+\min(4,1)+\min(3,5)+\min(1,1)=7.
Sample Input 2
4 4 27 6 1 10 42 87 6 21 33
Sample Output 2
317
Sample Input 3
5 7 583272014892537201 763832259 547096173 408327452 685495693 212251318 850800766 845647066 240229336 648345577 691868483 740301913 740485849
Sample Output 3
931208848
Compute modulo 998244353.