Grox的序列四¶
- 参考时间限制：1.0 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：1024 MB。
- 参考评测环境与测量
背景故事¶
知识可以透过探索、观察、收集经验资料、推论、假说和假说实验等过程来获得。
——科学之书3（《Spore》，英文资料）
解决了第二道序列问题后，Grox 发现了一种神奇的算法，能够生成一种神奇的序列。这次，序列的构造同时用到了按位异或、按位或与按位与。
Grox 想知道这个序列的值，但为了避免输出过多，只请你计算三个汇总值。
形式化问题描述¶
给定非负整数 \(n\) 和两组整数 \(a_0,\ldots,a_n\) 、\(b_0,\ldots,b_n\) .令 \(P=1004535809\) .
对 \(0\le t\le n\) ，定义
\[
C_t=\sum_{\substack{0\le i,j\le n\\i+j\le n\\i\mathbin{\mathrm{XOR}}j=t}}a_i b_j+\sum_{\substack{0\le i,j\le n\\i+j\le n\\i\mathbin{\mathrm{OR}}j=t}}a_i b_j+\sum_{\substack{0\le i,j\le n\\i+j\le n\\i\mathbin{\mathrm{AND}}j=t}}a_i b_j
\]
\(\mathrm{XOR}\) 、\(\mathrm{OR}\) 、\(\mathrm{AND}\) 分别表示按位异或、按位或、按位与。三个求和各自计数；同一有序数对可在不同求和中贡献。
对 \(r=0,1,2\) ，计算
\[
V_r=\left(\sum_{\substack{0\le t\le n\\t\equiv r\pmod3}}C_t\right)\bmod P
\]
空和为 \(0\) .输出每个结果的最小非负余数。
输入格式¶
第一行一个整数 \(n\) .第二行 \(n+1\) 个整数 \(a_0,\ldots,a_n\) ；第三行 \(n+1\) 个整数 \(b_0,\ldots,b_n\) .
输出格式¶
输出三行，依次为 \(V_0,V_1,V_2\) .
样例¶
样例 1¶
输入¶
2
1 2 3
3 2 1
输出¶
31
24
20
样例 2¶
输入¶
0
2
3
输出¶
18
0
0
样例 3¶
输入¶
3
1 0 2 3
0 4 1 0
输出¶
29
8
2
样例解释¶
样例一中 \(C_0=31,C_1=24,C_2=20\) .样例二中，唯一数对在三个求和中各贡献 \(6\) ，所以 \(V_0=18\) .
数据范围与保证¶
对 100% 数据：
\(0\le n\le2^{20}-1\) ；\(0\le a_i,b_i\le10^9\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |