三校集训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$将某位取反。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇