该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P11431 [COCI 2024/2025 #2] 差异 / Različitost

题目背景

译自 COCI 2024/2025 #2 T3。$\texttt{2s,0.5G}$。满分为 $90$。

题目描述

给定无限长的，周期长度为 $n$ 的非负整数序列 $a$ 的前 $n$ 项 $a_1,a_2,\cdots,a_n$。

给定无限长的，周期长度为 $m$ 的非负整数序列 $b$ 的前 $m$ 项 $b_1,b_2,\cdots,b_m$。

给定正整数 $k$，求出 $\displaystyle \left(\sum_{i=1}^k a_i\oplus b_i\right)\bmod \left(10^9+7\right)$。

输入格式

第一行，三个正整数 $n,m,k$。

第二行，$n$ 个正整数 $a_1,\cdots,a_n$。

第三行，$m$ 个正整数 $b_1,\cdots,b_m$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

3 2 10
1 6 4
5 2

输出 #1

33

输入输出样例 #2

输入 #2

10 5 30
5 16 2 10 7 2 4 20 5 12
4 11 14 23 5

输出 #2

435

说明/提示

对于 $100\%$ 的数据，保证：

• $1\le n,m\le 2\times 10^5$；
• $1\le k\le 10^{18}$；
• $0\le a_i,b_i\le 10^{18}$。

• 特殊性质 A：$n=m$。
• 特殊性质 B：$n=1$。

#5700. 「COCI 2024/2025 #2」Različitost

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #2 T3「Različitost」

给定两个无限的整数周期序列 $a_{i}$ 和 $b_{i}$，分别由长度为 $n$ 和 $m$ 的周期定义。这意味着给定自然数 $n$ 和 $m$，以及数字 $a_{1}, a_{2}, \ldots, a_{n}$ 和 $b_{1}, b_{2}, \ldots, b_{m}$，对于每个自然数 $i$，满足 $a_{i}=a_{i+n}$ 和 $b_{i}=b_{i+m}$。

此外，给定一个自然数 $k$，我们定义这两个序列的多样性为对于每个 $i=1, 2, \ldots, k$，求和 $a_{i} \oplus b_{i}$。（这里 $\oplus$ 表示按位异或运算，即在二进制数字不同的位置上产生 $1$。例如，$5 \oplus 3=(101)_{2} \oplus (011)_{2}=(110)_{2}=6$。）

你的任务是计算给定序列的多样性。

输入格式

第一行包含 $n, m$ 和 $k$ $(1 \leq n, m \leq 2 \cdot 10^{5}, 1 \leq k \leq 10^{18})$，它们是题目描述中的数字。

第二行包含 $n$ 个整数 $a_{1}, \ldots, a_{n}$ $(0 \leq a_{i} \leq 10^{18}, i=1, 2, \ldots, n)$。

第三行包含 $m$ 个整数 $b_{1}, \ldots, b_{m}$ $(0 \leq b_{i} \leq 10^{18}, i=1, 2, \ldots, m)$。

输出格式

因为答案可能非常大，请在单行中输出答案除以 $10^{9}+7$ 的余数。

样例 1

输入

3 2 10
1 6 4
5 2

输出

33

样例 2

输入

10 5 30
5 16 2 10 7 2 4 20 5 12
4 11 14 23 5

输出

435

数据范围与提示

详细子任务附加限制及分值如下表所示。