12801 大凤号装甲空母

思路

先将题目待求式子打表观察,发现将偶数项+1后的数列满足递推式:

a[i]=a[i-2]+a[i-1]

因此可以用矩阵快速幂求出前两项为1,3,递推式为上式的数列,如果询问到偶数项,答案在取模意义下减一,奇数项直接输出。
注意输入n小于2的情况会导致矩阵快速幂传入负数,所以需要特殊处理一下。
以及注意p有可能为1,输出时要注意取模。

赛后推导

1.斐波那契数列通项公式:

F\left(n\right) =\frac{1}{\sqrt 5} \times \left[ \left( \frac{1+\sqrt5}{2} \right)^n-\left( \frac{1-\sqrt5}{2} \right)^n \right]

2.斐波那契数列二倍项的关系:

\frac{F\left(2n\right)}{F\left(n\right)}=F\left(n-1\right)+F\left(n+1\right)

将第2n项使用平方差公式展开:

等号左侧即为答案,等号右侧的第一项a[n]即为上文构造出的前两项为1,3,满足上述递推式的数列,接下来看第二项。
由于 -1<\displaystyle\frac{1-\sqrt5}{2} <0 ,因此\displaystyle\left|\left( \frac{1-\sqrt5}{2} \right)^{n}\right|<1,因此有:

  1. 当n为奇数时,0<\displaystyle-\left( \frac{1-\sqrt5}{2} \right)^{n}<1
  2. 当n为偶数时,-1<\displaystyle-\left( \frac{1-\sqrt5}{2} \right)^{n}<0

所以n为奇数时\displaystyle\lfloor\left( \frac{1+\sqrt5}{2} \right)^{n}\rfloor=a[n],n为偶数时\displaystyle\lfloor\left( \frac{1+\sqrt5}{2} \right)^{n}\rfloor=a[n]-1

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int mod=1e9+7;
const int N=50;
const int M=5;
int K=2;
struct Matrix
{
    ll a[M][M];
};
Matrix mul(Matrix &a,Matrix b)
{
    Matrix tmp;
    for(int i=0;i<=K;i++)
        for(int j=0;j<=K;j++)
        tmp.a[i][j]=0;
    for(int i=1;i<=K;i++)
        for(int j=1;j<=K;j++)
        for(int k=1;k<=K;k++)
        tmp.a[i][j]=(tmp.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
    return tmp;
}
Matrix pow(Matrix &a,ll b)
{
    Matrix ans;
    for(int i=1;i<=K;i++)
        for(int j=1;j<=K;j++)
        ans.a[i][j]=i==j?1:0;
    while(b)
    {
        if(b&1) ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}
int main()
{
    //打表找规律部分
    /*long double d=5;
    for(int i=1;i<=20;i++)
    {
        printf("%lf %lf\n",
        pow((sqrt(5)+1)/2.0,i),pow((sqrt(5)-1)/2.0,i));
        a[i]=floor(pow((sqrt(5)+1)/2.0,i));
        cout<<a[i]<<endl;
    }
    return 0;*/
    ll n,p;
    scanf("%lld%lld",&n,&p);
    if(n<=1)
    {
        cout<<1ll%p;
        return 0;
    }
    if(n==2)
    {
        cout<<2ll%p;
        return 0;
    }
    mod=p;
    Matrix a;
    a.a[1][1]=a.a[1][2]=a.a[2][1]=1;
    a.a[2][2]=0;
    Matrix b;
    b.a[1][1]=3;
    b.a[2][1]=1;
    Matrix ans,tmp;
    tmp=pow(a,n-2);
    ans=mul(tmp,b);
    if(n%2==1) printf("%lld",ans.a[1][1]%p);
    else printf("%lld",((ans.a[1][1]-1)%p+p)%p);
    return 0;
}