【题解】牛牛的神奇数列

题意

给你一个数列的递推式子，求第n项是多少。

其中为完全平方数，并给你a和b的值

题解

题解一

对于这个常系数递推方程，我们可以求它的特征方程来求得通项。
有递推方程，可以得到特征方程

求得两个根为:
所以通项为
我们带入和可以得到
所以通项就为
而且题目保证为完全平方数所以直接套一个快速幂就可以解决这个问题。

题解二

对于这类求解线性递推的问题，可以用矩阵快速幂来求解。那么我们可以构造矩阵
但是由于数据量较大直接套用矩阵乘法的会由于常数过大而超时，需要对矩阵乘法优化一下，矩阵是的，也不大所以我们手动直接循环展开矩阵即可。

    c.m[0][0]=(a.m[0][0]*b.m[0][0]+a.m[0][1]*b.m[1][0])%mod;
    c.m[0][1]=(a.m[0][0]*b.m[0][1]+a.m[0][1]*b.m[1][1])%mod;
    c.m[1][0]=(a.m[1][0]*b.m[0][0]+a.m[1][1]*b.m[1][0])%mod;
    c.m[1][1]=(a.m[1][0]*b.m[0][1]+a.m[1][1]*b.m[1][1])%mod;

复杂度

时间复杂度为
空间复杂度为

代码

代码一

#include<bits/stdc++.h>
#define MAX 2
using namespace std;
typedef struct {
long long m[MAX][MAX];
}Matrix;
Matrix P={0,0,1,0};
Matrix I={1,0,0,1};
const int mod=1e9+7;
Matrix Matrixmul(Matrix a,Matrix b)
{
    Matrix c;
    c.m[0][0]=(a.m[0][0]*b.m[0][0]+a.m[0][1]*b.m[1][0])%mod;
    c.m[0][1]=(a.m[0][0]*b.m[0][1]+a.m[0][1]*b.m[1][1])%mod;
    c.m[1][0]=(a.m[1][0]*b.m[0][0]+a.m[1][1]*b.m[1][0])%mod;
    c.m[1][1]=(a.m[1][0]*b.m[0][1]+a.m[1][1]*b.m[1][1])%mod;
    return c;
}
Matrix quickpow(long long n)
{
    Matrix m=P,b=I;
    while(n>0)
    {
        if(n%2==1)
            b=Matrixmul(b,m);
        n=n/2;
        m=Matrixmul(m,m);
    }
    return b;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long n,a,b;
        scanf("%lld%lld%lld",&n,&a,&b);
        P.m[0][0]=2*a%mod;
        P.m[0][1]=b%mod;
        long long s=a*a+b;
        long long mid=sqrt(s);
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        else if(n==1)
        {
            long long f1=2*mid%mod;
            printf("%lld\n",f1);
            continue;
        }
        else
        {
            Matrix A=quickpow(n-1);
            long long f1=2*mid%mod;
            long long ans=A.m[0][0]*f1%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

代码二

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long quickmod(long long a,long long b)
{
    a=a%mod;
    long long ans=1;
    while(b>0)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long n,a,b;
        scanf("%lld%lld%lld",&n,&a,&b);
        long long s=a*a+b;
        long long mid=sqrt(s);
        long long ans=(quickmod(a+mid,n)-quickmod(a-mid,n)+mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}