萃香的新年宴会第一题题解#1萃香的请柬

# 萃香的新年宴会 #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，私信我可能看不见