#P5879. 廻廻奇譚

    ID: 6422 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-2-adic 赋值lowbit奇偶性分析同余的加减乘运算

廻廻奇譚

题目描述

对每组参数 a,b,ca,b,c,以该组的 cc 为常数,定义

$$f(x,k)= \begin{cases} x^{2c}\oplus c, & k=1,\\ f(x^{2c}\oplus c,k-1), & k>1. \end{cases}$$

其中 ⊕\oplus 表示按位异或。求每组的 lowbit⁡(f(a,b))\operatorname{lowbit}(f(a,b))。lowbit⁡(x)\operatorname{lowbit}(x) 是 xx 的二进制最低位 11 对应的权值,lowbit⁡(0)=0\operatorname{lowbit}(0)=0。

输入格式

第一行两个整数 T,typT,\mathrm{typ},表示数据组数和生成方式。

  • 当 typ=0\mathrm{typ}=0,接下来 TT 行,每行三个整数 a,b,ca,b,c。
  • 当 typ=1\mathrm{typ}=1,接下来只有一个无符号 64 位整数 seed\mathrm{seed}。依次调用三次生成函数,得到每组 a,b,ca,b,c,共生成 TT 组。每次调用对 64 位无符号状态执行下列变换,左移时溢出的高位丢弃。
seed ^= seed >> 7;
seed ^= seed << 13;
seed ^= seed >> 17;
return seed % 1000000000000000000ULL + 2;

此处的模数写法与原样例程序的 C++ 实际取值一致。下发模板 loop_muban.cpp 实现了相同的生成过程。

输出格式

输出一行两个非负整数,依次为 TT 组答案的按位异或和、算术和对 2642^{64} 取模的结果。

样例 1

1 0
5 2 4
1 1

样例 2

1 0
1000000000000000000 1000000000000000000 1000000000000000000
262144 262144

原题另在下发文件中提供样例 3、4。

数据范围

1≤T≤1071\le T\le10^7,typ∈{0,1}\mathrm{typ}\in\{0,1\},当 T>106T>10^6 时保证 typ=1\mathrm{typ}=1。对直接输入的数据,1<a,b,c≤10181<a,b,c\le10^{18}。

子任务 分值 附加限制
1 10 T=1T=1,a,b,c≤2a,b,c\le2
2 a,b,c≤10a,b,c\le10
3 40 cc 为偶数
4 无

原 PDF 题面