#6692. 「MtOI2019」幻想乡数学竞赛

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: disangan233

题目描述

一年一度的幻想乡数学竞赛 (thMO) 又要开始了。

幻想乡中学习数学的少 (lao) 女 (tai) 们 (po) 和冰之妖精 baka 一起准备着 thMO。

但是在那一刻,幻想乡日复一日的宁静被打破了。

广播里,播放起了死亡的歌曲!

在那一刻,人们又回想起了被算数支配的恐惧。

就剩下 baka,baka,baka,baka 的声音在幻想乡里回荡。


河城 荷取 (Kawashiro Nitori) 正坐在 thMO2019 的考场上!

因为荷取有着她的超级计算机,在成功地用光学迷彩覆盖了计算机之后,荷取在 thMO2019 的考场上所向披靡。

  • 荷取用她的超级计算机 0 \,\mathrm{ms} 跑出了这么一道题:

    • \exists \{ a_n\} (n=0,1,\cdots ,10^{18}) ,已知 a_0=2,a_1=5,a_{n+2}=3a_{n+1}-2a_n ,求 a_n\bmod 10^{9}+7
  • 荷取:显然,这个题可以用矩阵乘法 + 快速幂,可以 O(\log n) 水过去,差不多就这样:

\begin{bmatrix} a_n & a_{n+1} \end{bmatrix}=\begin{bmatrix} a_1 & a_2 \end{bmatrix} \times \begin{bmatrix} 3 & 1 \\ -2 & 0 \end{bmatrix}^n

但是荷取遇到了一道她不会的题,她正在寻求你的帮助呢!


存在一个数列 \{ a_n\} (n\in \{ 0,1,2,\cdots ,2^{64}-1\} )

已知 a_0=-3,a_1=-6,a_2=-12,a_n=3a_{n-1}+a_{n-2}-3a_{n-3}+3^n

  • 现在给你一个非负整数 n ,令 p=10^{9}+7 ,请你求出 a_n \bmod p

  • 注:若 a_n<0 ,请输出 (a_n \bmod p+p)\bmod p

为了更充分地考验你的水平,荷取设置了 T 组询问。

  • 为了在某种程度上减少你的输入和输出量,我们采用以下的代码来生成询问:
namespace Mker
{
//  Powered By Kawashiro_Nitori
//  Made In Gensokyo, Nihon
	#include<climits>
	#define ull unsigned long long
	#define uint unsigned int
	ull sd;int op;
	inline void init() {scanf("%llu %d", &sd, &op);}
	inline ull ull_rand()
	{
		sd ^= sd << 43;
		sd ^= sd >> 29;
		sd ^= sd << 34;
		return sd;
	}
	inline ull rand()
	{
		if (op == 0) return ull_rand() % USHRT_MAX + 1;
		if (op == 1) return ull_rand() % UINT_MAX + 1; 
		if (op == 2) return ull_rand();
	}
}

在调用 Mker::init() 函数之后,你第 i 次调用 Mker::rand() 函数时返回的便是第 i 次询问的 n_i

在这里给出 op 的限制:

  • 如果 op=0 ,满足 n_i \leq 2^{16}

  • 如果 op=1 ,满足 n_i \leq 2^{32}

  • 如果 op=2 ,满足 n_i \leq 2^{64}-1

为了减少你的输出量,你只需要输出所有询问答案的异或和

输入格式

第一行三个整数,输入 T seed op

输出格式

第一行一个整数,输出 T 组询问的答案的异或和

样例

样例输入 1
142857 1145141919 0

样例输出 1

562611141

样例输入 2

142857 1145141919 1

样例输出 2

894946216

样例输入 3

142857 1145141919 2

样例输出 3

771134436

数据范围与提示

子任务

测试点编号 T seed op
1 \leq 10^7 =0 2
2-3 \leq 5\times 10^6 =5201314 0
4-5 \leq 10^6 \leq 2^{32}-1 1
6 \leq 5\times 10^6 2
7 \leq 8\times 10^6
8-10 \leq 10^7
11 \leq 2\times 10^7 0
12 =1145141919 1
13-20 \leq 5\times 10^7 \leq 2^{32}-1 2

题目来源

迷途之家 2019 联赛 (MtOI2019) T4

出题人:disangan233

验题人:suwakow