萃香的新年宴会第一题题解#1萃香的请柬
Wy12121212
2018-03-10 15:49:38
# 萃香的新年宴会 #1 萃香的请柬
## by Wy12121212
[题目链接](https://www.luogu.org/problemnew/show/U20836)
题意:
一串序列由01组成,**初始状态随机**,每次变换序列中原来的‘1’变为‘10’,原来的‘0’变为‘1’,在经过无限次变换之后试求闭区间[l,r]间的‘1’的数量。
**本题做题难度:** _普及+/提高-_
**本题思考难度:** _提高+?_
**考查知识点:**收敛数列,斐波那契,~~找规律~~数学归纳法
看到这道题时你可能会蒙住,所以让我们先来简化一下题意:
一串序列由01组成,**初始序列为‘1’**,每次变换序列中原来的‘1’变为‘10’,原来的‘0’变为‘1’,在经过无限次变换之后试求闭区间[l,r]间的‘1’的数量。
然后对于这种数学题我们当然要愉快地打表啦
t=0:1
t=1:10
t=2:101
t=3:10110
t=4:10110101
......
到这里你可能已经发现数列的长度和其中‘1’的个数都是斐波那契数列,即fib[i]长度的数列对应fib[i-1]个‘1’
**严格证明:**
t次变换增加的‘1’由t-1次变换的‘0’和t-1次变换的‘1’得到,而t-1次变换的‘0’由t-2次变换的‘1’分裂得到,所以$num_1[t]=num_1[t-1]+num_1[t-2]$,而长度的证明亦同理。
那么问题就变得简单一些了,相信很多人直接就打出了正解,即将i递归拆分为若干个斐波那契数,每一次拆分(i-=fib[k])时ans[i]+=fib[k-1],然后差分一下输出ans[r]-ans[l-1]100分就到手了(注意边界和l=0的情况)
然而,这道题如果做到这里是没有价值的,因为
### 1.你没有证明拆分的正确性
### 2.这只是初始状态为'1'的特殊情况,没有推广为一般情况
**1.证明拆分的正确性:**
这里要用一个概念斐波那契进制,即任何一个正整数可以被拆分成若干个互异的斐波那契数(fib[0]=1,fib[1]=2),比如说4=fib(101),至于为什么请各位自己探究。
**2.推广到一般情况(初始不一定为‘1’):**
这里引用一下极限的概念胡诌一下:当t不断增加趋近于正无穷的时候,这个数列呈收敛态(**你可以理解为函数的波动渐渐趋于平稳**),而当t≥s时(s为收敛极限)你可以近似认为函数在[0,+∞]之间确定下来,当然,鉴于此题数据范围极小,收敛极限也不会很大。而我们要计算的就是这个收敛后的序列的情况。
**但是函数收敛的趋势如何?**
下面说人话:经过无限长的时间后,长度为[0,$2^{63}-1$]的数列就是由第一个数扩展很多次而来的(**你可以形象地认为后面的数及其扩展被第一个数挤出了这个范围**),如果第一个数开始时为‘1’,则与特殊情况完全一致,若为‘0’,则变换一次变为‘1’后与特殊情况完全一致。
## 所以你惊喜的发现,无论初始状态如何,最后序列的状态都不会受到任何影响。
至此,得证。
总结:这是一道很好的题,如果要严格解题的话思维难度很高,如果找规律的话也可以切掉(不建议)
AC代码
```cpp
while(q--)
{
scanf("%lld%lld",&a,&b);a--;
long long ans=0;
for(int i=91;i>=0;i--)
{
if(a>=f[i]&&b>=f[i])a-=f[i],b-=f[i];
else if(a>=f[i])a-=f[i],ans-=f[i-1];
else if(b>=f[i])b-=f[i],ans+=f[i-1];
}
printf("%lld\n",ans);
}
```
如果你抄袭的话请便,我知道你会喜欢棕名的
如果你有任何问题,请**加入我的团队**发帖提问或者加我的qq,私信我可能看不见