FZU Problem 2198 快来快来数一数(矩阵快速幂 卡常数 +优化)

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2198

Problem Description

n个六边形排成一行，相邻两个六边形共用一条边，如下图所示：

记这个图形的生成树个数为t(n)（由于每条边都是不同的，不存在同构的问题）。那么t(1)=6，t(2)=35……

给出n，求mod 1000000007

 Input

第一行给出数据组数T。

之后每一行给出一个正整数n。

T大约为50000，n<=10^18。

 Output

每组数据输出一行答案。

 Sample Input

2212345678987654321

 Sample Output

41733521876

 Source

FOJ有奖月赛-2015年10月

PS:

很容易写出通项公式为：

a[i] = 6*a[i-1] - a[i-2] +1;

但是这题的n很大T也很大!会卡常数！

普通的矩阵快速幂是会超时的；

这时就需要用到快速幂的优化了！

但是我直接在普通的矩阵快速幂上加了优化，还是会超时，

在提交了多次后，终于有一次过了而且时间是恰好1000ms！

然后再用相同的代码提交就是T！

下面给出一个矩阵快速幂优化的模板；

用这个模板，时间直接减少的500+ms！

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const LL mod = 1000000007;

struct Matrix
{
    int row,col;
    LL m[4][4];
    void init(int row, int col)
    {
        this->row = row;
        this->col = col;
        for(int i = 0; i < row; ++i)
            for(int j = 0; j < col; ++j)
                m[i][j] = 0;
    }
} A, pp[66], ans;

Matrix operator*(const Matrix & a, const Matrix& b)
{
    Matrix res;
    res.init(a.row,b.col);
    for(int k = 0; k < a.col; ++k)
    {
        for(int i = 0; i < res.row; ++i)
        {
            if(a.m[i][k] == 0 ) continue;
            for(int j = 0; j < res.col; ++j)
            {
                if(b.m[k][j] == 0 ) continue;
                res.m[i][j] = (a.m[i][k]*b.m[k][j] + res.m[i][j])%mod;
            }
        }
    }
    return res;
}
void init()
{
    Matrix qq;
    A.init(3,1);
    A.m[0][0] = 7;
    A.m[1][0] = 1;
    A.m[2][0] = 1;

    qq.init(3,3);
    qq.m[0][0] = 6;
    qq.m[0][1] = -1;
    qq.m[0][2] = 1;
    qq.m[1][0] = 1;
    qq.m[2][2] = 1;
    pp[0] = qq;
    for(int i = 1; i < 64; i++)
        pp[i] = pp[i-1] * pp[i-1];
}

void Cal(LL a)
{
    for(int i=0; a; i++,a>>=1)
    {
        if(a&1)
        {
            ans = pp[i]*ans;
        }
    }
    return ;
}

int main()
{
    int T;
    LL n;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d",&n);
        ans = A;
        Cal(n-1);
        printf("%I64d\n",(ans.m[0][0]-1+mod)%mod);
    }
}

最后给出普通的矩阵快速幂+优化代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL __int64
struct Matrix
{
    LL m[4][4];
} I,A,B,T;
LL n, c;
int ssize = 3;
const LL mod = 1000000007;

Matrix Mul(Matrix a,Matrix b)
{
    int i, j, k;
    Matrix c;
    for(i = 1; i <= ssize; i++)
    {
        for(j = 1; j <= ssize; j++)
        {
            c.m[i][j]=0;
            for(k = 1; k <= ssize; k++)
            {
                c.m[i][j]+=(a.m[i][k]*b.m[k][j]);
                c.m[i][j]%=mod;
            }
        }
    }
    return c;
}

Matrix quickpagow(LL n)
{
    memset(I.m,0,sizeof(I.m));
    for(int i = 1; i <= ssize; i++)
    {
        //单位矩阵
        I.m[i][i]=1;
    }
    Matrix m = A, b = I;
    while(n > 0)
    {
        if(n & 1)
            b = Mul(b,m);
        n = n >> 1;
        m = Mul(m,m);
    }
    return b;
}
int main()
{
    memset(A.m,0,sizeof(A.m));
    memset(B.m,0,sizeof(B.m));

    A.m[1][1] = 6;//初始化等比矩阵
    A.m[1][2] = -1;
    A.m[1][3] = A.m[2][1] = A.m[3][3] = 1;

    B.m[1][1] = 7;
    B.m[2][1] = 1;
    B.m[3][1] = 1;

    Matrix haha[80];
    haha[1] = A;
    for(int i = 2; i < 70; i++)
    {
        haha[i] = Mul(haha[i-1], haha[i-1]);
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d",&n);
        if(n==1)
        {
            printf("6\n");
            continue;
        }
        if(n==2)
        {
            printf("41\n");
            continue;
        }
        Matrix C;
        memset(C.m,0,sizeof(C.m));
        n--;
        for(int i = 1; i <= ssize; i++)
        {
            C.m[i][i] = 1;
        }
        for(int i = 1; n; i++,n>>=1)
        {
            if(n&1)
            {
                C = Mul(C,haha[i]);
            }
        }
        T = Mul(C,B);
        printf("%I64d\n",(T.m[1][1]-1+mod)%mod);
    }
    return 0;
}