#P9634. 友谊序列

    ID: 6248 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1600普及+/提高-异或抵消双射计数奇偶性分析

友谊序列

题目描述

Mike 和 Joi 在玩一个游戏,他们各有一个长度为 nn 的数组,Mike 的数组叫 aa,Joi 的数组叫 bb。 已知他们这 2n2n 个数互不相同,设这 2n2n 个数构成的集合为 SS。 现在他们想知道,可以构成多少对 (i,j)(i,j) 满足 ai⊕bi∈Sa_i \oplus b_i \in S。

当为奇数时,输出 1!,表示 Mike 获胜;当为偶数时,输出 0!,表示 Joi 获胜。请根据题目给出的数据输出结果。

输入格式

第一行一个整数 TT,表示数据组数。

每组数据内,第一行一个正整数 nn。

每组数据内,第二行 nn 个正整数,表示数组 aa。

每组数据内,第三行 nn 个正整数,表示数组 bb。

输出格式

输出 TT 行,每行一个字符串 0! 或者 1!,表示谁胜利了。

样例

1
3
1 2 3
4 5 6
0!

1⊕4=51\oplus 4=5,属于;1⊕5=41\oplus 5=4,属于;1⊕6=71\oplus 6=7,不属于;

2⊕4=62\oplus 4=6,属于;2⊕5=72\oplus 5=7,不属于;2⊕6=42\oplus 6=4,属于;

3⊕4=73\oplus 4=7,不属于;3⊕5=63\oplus 5=6,属于;3⊕6=53\oplus 6=5,属于。

共 66 对 (i,j)(i,j) 满足条件,输出 0!。

数据范围

这里用 vv 表示数组中最大的数字。

对于前 30%30\% 的数据,n≤10n\le 10。

对于前 70%70\% 的数据,n≤2000n\le 2000。

对于前 90%90\% 的数据,v≤106v\le 10^6。

对于 100%100\% 的数据,n≤2×105n\le 2\times 10^5,v≤109v\le 10^9,T≤3T\le 3。