自动搬运

查看原文

来自洛谷，原作者为

	the_Death AFO

搬运于2025-08-24 21:55:11，当前版本为作者最后更新于2019-11-04 21:17:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

---

P3981 琅泽难题

Luogu

或许会有更好的阅读体验

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

---

题目解答

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

• 例如，若有一层为(不一定合法)：1113115
• 若按照$A$规律对其进行描述，则就是：11111113111115->1个1(x3遍)+1个3+1个1(x2遍)+1个5。
• 如果按照$B$规律对其进行描述则为：31132115->3个1+1个3+2个1+1个5

然后寻找第$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$之前，我们先阐述两条结论：

• 在$A$规律下，只会有$1$ $X$这样的数据，正确性显然
• 在$B$规律下，会有$1$ $X$， $X$ $Y$这样的数据，正确性显然

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

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			4	7	12	20	33	54
7数量		0	1	2	4	7	12	20	33
潜7	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

官方题解