#1614. Nim 积

Nim 积

题目描述

这是一道模板题。

对于两个非负整数 x,yx, y 我们定义其 Nim 积 xyx\otimes y

$$x \otimes y = \operatorname {mex} \{ (a\otimes b) \oplus (a\otimes y) \oplus (x\otimes b) \mid 0\le a < x \wedge 0\le b < y \} $$

其中 \oplus 是异或运算,mex\operatorname{mex} 是集合中不存在的最小非负整数。

输入格式

第一行输入四个整数 T,SA,SB,SCT, \mathrm{SA}, \mathrm{SB}, \mathrm{SC}

为了测试效率,询问数量 TT 可能很大,使用如下代码生成询问的输入:

unsigned int SA, SB, SC;
unsigned int rng() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}

在接下来 TT 组询问中,设 lastans\mathrm{lastans} 最初为 00,则按顺序有

unsigned int x = rng() + lastans;
unsigned int y = rng();
lastans = nim_mul(x, y);

如此进行 TT 次循环。

输出格式

输出一行一个整数,表示最后一组解的答案。

样例

5 171380702 78283356 95463589
1145338263

各组询问的 x,yx, y 解码后以及 Nim 积分别是:

2569590012376274030=32929940256959001\otimes 2376274030 = 32929940 20874170673383958306=15910927062087417067\otimes 3383958306 =1591092706 20043909481462129087=6017531572004390948\otimes 1462129087 =601753157 14664709654216679711=11152645441466470965\otimes 4216679711 =1115264544 945607294273456727=114533826394560729\otimes 4273456727 =1145338263

数据范围与提示

生成的数据均在 2322^{32} 范围以内,故保证 0x,y<2320\le x, y < 2^{32}

四组数据中的 TT 分别为 10,1000,3×104,3×10710, 1000, 3\times 10^4, 3\times 10^7