题目描述

输入

输出

样例输入

5 97

样例输出

11

提示

 

 

 

 

题解

先不管p，通过列举前面几项，不难发现当i为偶数时，a[i]=a[i-1]+a[i-2]，当i为奇数时，a[i]=a[i-1]+a[i-2]+1,具体证明还不会，希望有大佬能在讨论区讲讲

知道了a[i]的通项后，我们可以通过矩阵乘法的快速幂log(n)来求出答案。

具体怎么做，我们可以两项两项的来做，最后再判断一下n的奇偶性就可以了。

不过我是用3维矩阵来做的

刚开始的ans为

0	0	0
0	0	0
1	2	1

ans[3][1]表示a[i-1],ans[3][2]表示a[i]  

tmp为

1	1	0
1	2	0
1	1	1

刚开始Matrix_pow(n/2-1,p)，具体为什么是这样可以代一个n=2进去，这样Matrix_pow不会做，再判断n为偶数，那么答案就是ans[3][2]，发现是正确的

 

做完Matrix_pow后，判断n为奇数就再乘一个矩阵temp为

0	1	0
1	1	0
0	1	1

最后答案就是ans[3][2]

不过这里你要特判一下n=0和n=1的情况，我就是被n=0给坑了，害得我找了1个小时的错

1 #include
       
         2 #define ll long long 3 using namespace std; 4 ll n,p; 5 ll tmp[4][4],temp[4][4],ans[4][4],c[4][4]; 6 void Matrix_mul(ll a[4][4],ll b[4][4]){ 7     for (int i=1;i<=3;i++) 8         for (int j=1;j<=3;j++){ 9             c[i][j]=0;10             for (int k=1;k<=3;k++)11                 c[i][j]=(c[i][j]+a[i][k]%p*b[k][j]%p)%p;12         }13 }14 void Matrix_pow(ll n){15     while (n>0){16         if (n%2){17             Matrix_mul(ans,tmp);18             memcpy(ans,c,sizeof(ans));19         }20         Matrix_mul(tmp,tmp); 21         memcpy(tmp,c,sizeof(tmp));22         n>>=1;23     }24 }25 int main(){26     scanf("%lld%lld",&n,&p);27     if (!n||n==1){ printf("%lld\n",1%p); return 0; }28     tmp[1][1]=1; tmp[1][2]=1; tmp[2][1]=1; tmp[2][2]=2; tmp[3][1]=1; tmp[3][2]=1; tmp[3][3]=1;29     ans[3][1]=1; ans[3][2]=2; ans[3][3]=1;30     temp[1][2]=1; temp[2][1]=1; temp[2][2]=1; temp[3][2]=1; temp[3][3]=1;31     Matrix_pow(n/2-1);32     if (n%2){33         Matrix_mul(ans,temp);34         memcpy(ans,c,sizeof(ans));35     }36     printf("%lld\n",ans[3][2]);37     return 0;38 }