QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[0]
Statistics

题目描述

这是一道模板题。

对于两个非负整数 x,y 我们定义其 Nim 积 xy

xy=mex{(ab)(ay)(xb)0a<x0b<y}

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

输入格式

第一行输入四个整数 T,SA,SB,SC

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

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;
}

在接下来 T 组询问中,设 lastans 最初为 0,则按顺序有

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

如此进行 T 次循环。

输出格式:

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

样例数据

样例输入

5 171380702 78283356 95463589

样例输出

1145338263

样例解释

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

  • 2569590012376274030=32929940
  • 20874170673383958306=1591092706
  • 20043909481462129087=601753157
  • 14664709654216679711=1115264544
  • 945607294273456727=1145338263

子任务

生成的数据均在 232 范围以内,故保证 0x,y<232

四组数据中的 T 分别为 10,1000,3×104,3×107