关键词:数学-数论 相关题目:萃香的请柬

题目背景

现在是宴会开始前一天 萃香的请柬

题目描述

    萃香在小时候就一直有一个梦想,就是邀请全乡居民一起参加宴会,在上次发动异变被灵梦退治之后她仍旧没有放弃,而是在元宵节前早早准备好了难以计数的请柬。     现在,宴会即将开始,萃香却还是有一大堆请柬没有送出。经过大数学家琪露诺的严谨推算,到2018年时幻想乡的居民数目已经远远超过了外界,而这就使得宴会的邀请变得极为困难。     但是,拥有"操纵密度程度的能力"的萃香可以分成大大小小的萃香一起去送请柬。由于小萃香的移动速度过慢,因此她决定只让大萃香曲去送请柬。     开始时有S只萃香,之后每过一秒每一个大萃香会分成一大一小两个萃香,与此同时上一次分出的小萃香会积聚能量变大为大萃香。     直观的说,下面是开始只有一个大萃香时前四秒的变化情况(大萃香用"B"表示,小萃香用"L"表示) 样例     (很容易看出,第一次的大萃香经过一秒后分成了一大一小两只萃香,之后一秒刚才分出的大萃香继续分裂,而刚才的小萃香长大为大萃香)     可是,我们这位"小小的百鬼夜行"发现了一个严重的问题:在经过无限长的时间后,萃香的数目太多了。于是她决定每一次只让一段区间内的大萃香去送请柬,而她现在想要知道每一次能够送出的请柬个数。     如果你能帮她完成这个任务,她就会送给你两个奖励——100分和宴会的请柬!

输入输出格式

输入格式:     第一行S个大写字母('B'或'L'),表示开始时萃香的状态     之后是一个整数n,表示询问的个数     接下来n行每行两个整数l,r表示询问的区间

输出格式:     共n行,每行一个整数k,表示区间[l,r]中大萃香的个数

题解

    题解:萃香的请柬-----by Wy12121212

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>    
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define drep(i,a,b) for(re i=(a);i>=(b);--(i))
int n;
char s[1000005];
long long ans,l,r,f[92];
inline void init(){
f[0]=1,f[1]=1;
rep(i,2,91) f[i]=f[i-1]+f[i-2];
}
int main(){
init();
gets(s);
scanf("%d",&n);
while(n--){
scanf("%lld%lld",&l,&r);
ans=0,--l;
drep(i,91,0){
if(l>=f[i]&&r>=f[i]) l-=f[i],r-=f[i];
else if(l>=f[i]) l-=f[i],ans-=f[i-1];
else if(r>=f[i]) r-=f[i],ans+=f[i-1];
}
printf("%lld\n",ans);
}
}