【题解】 Recursive sequence

矩阵快速幂。

题意：
一组数的递推公式如下：F(1)=a,F(2)=b,F(n)=F(n-1)+2* F(n-2)+ (n>2)。现要求出该序列中的第n个数。

思路：
由于n的值太大，直接递推不行，这里采用构造系数矩阵的方法。
本人目前的理解：当以递归得到数的效率太低时，可以研究递归过程，拆分或者合并公式中的数，研究两个过程的数之间的关系并建立一个矩阵，建立系数矩阵以系数矩阵的幂代替递归。诸如此类的还有求第n个斐波那契数。
观察发现递推过程中的数有：F(n),F(n-1),，而下一个递推过程中的数有：F(n+1),F(n), ，我们要想办法通过第一个过程得到第二个过程。发现第二个过程需要 ，因此要再加入,,n,1构造矩阵[F(n),F(n-1),,,,n,1]的系数矩阵。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=2147493647;//1e9+7;
const int maxn=1e5+9;
const ll maxx=1e12+9;

const int sz=7;
struct mat
{
    ll a[sz][sz];
};
ll t,a,b;

mat mul_mat(mat a,mat b)
{
    mat res;
    for(int i=0;i<sz;i++)
        for(int j=0;j<sz;j++)
        {
            res.a[i][j]=0;
            for(int k=0;k<sz;k++)
                res.a[i][j]=(res.a[i][j]+a.a[i][k]*b.a[k][j])%mol;
        }
    return res;
}
mat mat_q_pow(mat x,ll t)
{
    mat res;
    for(int i=0;i<sz;i++)
        for(int j=0;j<sz;j++)
            if(i==j) res.a[i][j]=1;
            else res.a[i][j]=0;
    while(t)
    {
        if(t&1) res=mul_mat(x,res);
        x=mul_mat(x,x);
        t>>=1;
    }
    return res;
}
ll cal(mat ar)
{
    return (ar.a[1][0]*b+ar.a[1][1]*a+ar.a[1][2]*16+ar.a[1][3]*8+ar.a[1][4]*4+ar.a[1][5]*2+ar.a[1][6])%mol;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&t,&a,&b);
        mat ar={
            1,2,1,4,6,4,1,
            1,0,0,0,0,0,0,
            0,0,1,4,6,4,1,
            0,0,0,1,3,3,1,
            0,0,0,0,1,2,1,
            0,0,0,0,0,1,1,
            0,0,0,0,0,0,1
                };
        ar=mat_q_pow(ar,t-1);
        if(t==1) printf("%lld\n",a);
        else if(t==2) printf("%lld\n",b);
        else printf("%lld\n",cal(ar));
    }
}