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

· · 题解

萃香的新年宴会 #1 萃香的请柬

by Wy12121212

题目链接

题意: 一串序列由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代码

    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，私信我可能看不见