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

「MtOI2019」幻想乡数学竞赛

题目描述

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

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

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

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

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

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


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

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

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

    • {an}(n=0,1,,1018)\exists \{ a_n\} (n=0,1,\cdots ,10^{18}),已知 a0=2,a1=5,an+2=3an+12ana_0=2,a_1=5,a_{n+2}=3a_{n+1}-2a_n,求 anmod109+7a_n\bmod 10^{9}+7
  • 荷取:显然,这个题可以用矩阵乘法 + 快速幂,可以 O(logn)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 $$

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


存在一个数列 {an}(n{0,1,2,,2641})\{ 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$。

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

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

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

  • 为了在某种程度上减少你的输入和输出量,我们采用以下的代码来生成询问:
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() 函数之后,你第 ii 次调用 Mker::rand() 函数时返回的便是第 ii 次询问的 nin_i

在这里给出 opop 的限制:

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

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

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

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

输入格式

第一行三个整数,输入 TTseedseedopop

输出格式

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

样例 1

142857 1145141919 0
562611141
142857 1145141919 1
894946216
142857 1145141919 2
771134436

数据范围与提示

子任务

测试点编号 TT seedseed opop
11 107\leq 10^7 =0=0 22
232-3 5×106\leq 5\times 10^6 =5201314=5201314 00
454-5 106\leq 10^6 2321\leq 2^{32}-1 11
66 5×106\leq 5\times 10^6 22
77 8×106\leq 8\times 10^6
8108-10 107\leq 10^7
1111 2×107\leq 2\times 10^7 00
1212 =1145141919=1145141919 11
132013-20 5×107\leq 5\times 10^7 2321\leq 2^{32}-1 22

题目来源

(MtOI2019) T4

出题人:disangan233

验题人:suwakow