题解 P3981 【琅泽难题】

· · 题解

这题是真的好，我是真的自己做不出来QAQ

P3981 琅泽难题

Luogu

或许会有更好的阅读体验

这在官方题解基础上，加上自己的一些理解所写，原题解见此题解最下方链接

题目解答

首先，由图可知，A规律是对上一层每一个数字进行一次描述，B是对上一层数字所构成的连续区间进行描述。

然后寻找第I层中由几个X的规律了

首先我们假设初始数据为a，以此来构造矩阵：(为方便记录，每一行最左侧为层数)

  1. a
  2. 1 1
  3. 1 1 1 a
  4. 3 1 1 a
  5. 1 3 1 1 1 1 1 a
  6. 1 1 1 3 5 1 1 a
  7. 1 1 1 1 1 1 1 3 1 5 1 1 1 1 1 a
  8. 7 1 1 3 1 1 1 5 5 1 1 a
  9. 1 7 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 5 1 5 1 1 1 1 1 a
  10. 1 1 1 7 5 1 1 3 7 1 1 5 1 1 1 5 5 1 1 a

此时，我们不难发现，当a达到一个阈值的时候，不会在同一层出现第二个a。我们此时要尝试找到这个阈值。

由上图的数据可猜测，这个阈值就是7。然后我们来证明一下

在证明阈值为7之前，我们先阐述两条结论：

请大家牢记这两条正确性显然(尤其是第一条)的结论，这对于我们之后的证明有大用。然后我们开始证明

  1. 这个琅琊阵中不会出现偶数(若a为偶数，则就只会出现一个偶数，即为a)
    • 考虑偶数出现的原因。
    • 首先由于琅琊阵的规律我们可知，只有在B规律下才可以出现偶数。那么我们假设在A规律下的那一层数据为：a个连续的b 和 n个连续的k 和 c个连续的d。我们要保证a{\neq}k且k{\neq}c。只有样才可以保证B在描述的时候，不会包含多余的数字。
      • 由于结论1，我们可知，a=c=1
      • 如果k{\neq}1的话，由于结论1，如果这个数字不是1的话，必然无法保证两两一致。所以k=1。
      • 如果k=1的话，保证c是偶数。那么后面的那个不同的数字为了不同，必然以1 d的形式出现，此时c就不是偶数
      • 如果c不是偶数，由以上观点可知k=1，且1的出现都是成双成对的，所以c必须是偶数
    • 由以上证明可知琅泽阵之中不存在偶数
  2. 琅泽阵之中不存在大于7的数字(除了a本身)
    • 假设它之中出现了9，如果连除了1，3，5，7和偶数以外的数字的最小值都无法出现，那么更大的数字就不可能出现了，这个正确性请感性了解一下
    • 如果这之中出现了9，那它必然是在B层出现的。那么代表A层之中有连续的9个1。也就是说再上一个B层之中，有连续的4个1和1个非1数字。由于B是描述一个连续区间的，所以这4个1无论如何都无法凑出，所以琅泽阵之中不可能出现9
    • 其余数字以此类推。故可得结论：琅泽阵之中除a外，不可能出现大于7的数字

至此，琅琊阵之中会出现的数字的讨论结束了。然后我们对3，5，7分别寻找出现的规律

  1. 当a{\neq}3且a>1的时候，整个琅琊阵只存在一个3
    • 在第3行后，若出现新的3，则需满足在A规律中出现3个单独连续的1(即这M3个1左右两边都没有1)，那么在此又往上一次的A规律中必须有两个连续的非1数，然而这并不可能，因为在分的时候，若出现两个连续的k和n(k，n>1)，则可能为
    • ①k个n，与该规律矛盾！
    • ②q个k，n个p，又与之矛盾！故往后不可能再出现新的3。
    • 而第四行出现的3是特殊情况，因为前两次的分恰好满足a单独存在，导致前一次出现连续三个1，而往后就没有了。

  2. 对于5，7进行讨论

    • 我们可以通过打表的方式得到5，7的规律。由于A的规律仅是对B的一种逐个描述，不会在序列之中添加除了1以外的其余的数字，所以这里我们只看B规律
    4 6 8 10 12 14 16 18 20
    潜5 1 1 2 3 5 8 13 21 34
    5数量 0 1 2 4 7 12 20 33 54
    7数量 0 0 1 2 4 7 12 20 33
    潜7 1 1 2 3 5 8 13 21 34
    • 注：潜5表示下一次B规律要增加的5，潜7表示往后第二次B要增加的7

然后我们可以惊喜的发现这里有斐波那契数列！

  • 事实上，5是由上一次B规律中两个单独连续的1演变而来的，演变来之后随之又增加了两个单独连续的1，也就是上一次B规律带来了1个5并埋下了一个潜5。
  • 那为什么是斐波那契数列呢？我们又发现7是由上两次B规律中两个连续的不等数得来的。而第4行由于3在在前面，可以视为前面有一个与它不等的数，因此埋下了一个潜7，在下一次B规律中，7并没有马上出现，而是演变成了3个1，此时由上一层演变而来的5又与3靠在了一起，埋下一个潜7，那么该行就有一个潜5一个潜7。
  • 也就是说，每一个潜5都会带来1个潜5和1个潜7，而不难发现，每一个潜7又会给下两行带来一个潜5和潜7。那么我们知道第四行是1个潜5和1个潜7，第六行由第四行的潜5得到1个潜5和1个潜7，而第八行由第六行的潜5得1个潜5和1个潜7，再由第四行的潜7得到1个潜5和1个潜7 。

UPDATE:此处Latex炸了，故放上图片

这时我们回想斐波那契数列的原本的提出：刚出生的兔子，要再长一个月才可以生出兔子。而潜7的增长方式与之相同。

总结以上，我们可知：潜5和潜7在每一层上都是相等的。但是潜5对后面没有影响，每一个潜7对其后面的第二次的B规律有影响，即F[N]=F[N-1]+F[N-2]

我们设2n层的5的数量为five[k](k=n),设斐波那契数列为F[i],那么2n层对应的潜5或潜7数量就是F[n]=F[k-1],故易得five[k]=five[k-1]+F[k-2]。(此处层数/2，仅仅是为了更好的编写程序，规律A不会改变非1数字的数目，所以不考虑A也是可以的)

所以最后第k的5数目的答案式是{five[k]={\sum_{i=1}^{k-2}(F[i])}}。对于7来讲，7的数目与上一次相同规律的5的数目是一样的。

至此，琅琊阵的规律全部解释完毕

程序构造

斐波那契数列的O(N)公式大家都知道，但是由于实现太少，所以这样的方法肯定不对。我们可以进一步考虑奇数项和偶数项的求和公式，即为

F[2n]=F[2n-1]+...+F[3]+F[1] F[2n+1]-1=F[2n]+...+F[4]+F[2]

但是仅仅依靠这两个公式，你还是会超时，你想到了还有一种公式，叫做二倍项公式

F[2n]=F[n-1]F[n]+F[n+1]F[n]

它可以化为

F[2n]=F[n]^{2}+2F[n]F[n-1] F[2n-1]=F[n]^{2}+F[n-1]^{2}

运用这个公式，你就可以获得AC的好结果

code

#include<iostream>
#include<cstdio>
using namespace std;
long long k,l,r,t,ans,a,p,q;
const long long mod=20171111;
inline void solve(long long a){
    if(a==2) k=1,l=1;//k->F[n],l->F[n-1]
    else if(a%2==0)
        solve(a/2),t=k*k+2*k*l,//二次项公式
        l=k*k+l*l,k=t;//二次项公式
    else if(a%2==1)
        solve(a-1),t=k+l,l=k,k=t;//普通公式
    k%=mod,l%=mod;
}
int main(){
    scanf("%lld%lld%lld",&a,&q,&p);
    if(p==5||p==7){
        q-=4,q/=2;
        if(p==7) q-=1;
        if(q>0) if(q%2==1)
                solve(q+2),ans+=k-1,ans%=mod;
        else solve(q),ans+=k,solve(q+1),
                ans+=k-1,ans%=mod;
        if(a==5||a==7) ans++;
        if(q<=0) putchar('0');
        else printf("%lld",ans);
    }
    else if(p==3)
        if(a!=3) if(q>3)
        putchar('1');else putchar('0');
        else if(q>3)
            putchar('2');else putchar('1');
        else if(a==p) putchar('1');
        else putchar('0');
}

最后，国际惯例，thankyou for your attention

官方题解