三校集训Part1 QZEZ Day6 B 题解

题意

一只萌萌的$ Galo $在沙滩上散步。突然,可怕的事情发生了!一只$ OvO $正在看着他!
为了逃脱被吃掉的命运,$Galo $稽中生智,扔出了自己研究了很久的一道题给昆西:
斐波那契数列是这样的一个数列
$F_0 = 1, F_1 = 2$
$F_i = F_{i−1} + F_{i−2}$
对于一个数,Galo 定义它的斐波那契表示为将其表示为一些斐波那契数的和, 并将其转化为二进制数。
例如 $G(9) = G(8 + 1) = G(F4 + F0) = (10001)_2 = 16 + 1 = 17$
那么$ 9 $就可以表示为$10001$。注意到这种表示并不是唯一的,例如$9$也可以表示为$ 1101$。为了使这种表
示唯一,$Galo $决定使用如下程序来得出表示

那么这样就可以使每个数有唯一的表示了!例如$ G(30) = (1010001)_2 = 64 + 16 + 1 = 81$
现在$ Galo $给出了一个区间$ [A, B]$, 他想知道$ G(A) \text{ xor } G(A + 1) .. \text{ xor } G(B – 1) \text{ xor } G(B) $是多少
昆西当然不知道怎么做了啊!这个问题就交给你了!
答案对$10^9+7$取模。
$A,B\leq 10^{15}$

思路

首先发现$A,B$范围很大,考虑使用异或前缀和。
那么答案就是$Ans_B \text{ xor } Ans_{A-1}$
定义$F(x)$表示$G(1) \text{ xor } G(2) \text{ xor }…\text{ xor } G(x)$
记$ P[i] = F({Fib}_i − 1)$
对于求一般的$ F(n)$, 对于求考虑逐位确定答案。
记$ i $为最大的$ Fib $数,满足$ {Fib}_i ≤ x$
那么第$ i $位的答案只与$ n − F ibi + 1 $的奇偶性有关
用$C++STL$中$bitset$实现

Code

顺便介绍一下$bitset$
常见操作有:位运算、$set$(将某位改为1),$reset$(将某位改为0),$flip$将某位取反。

暂无评论

发送评论


				
上一篇
下一篇