矩阵快速幂

typedef  struct
{
    LL  m[MAX][MAX];
}  Matrix;
LL a,b,c,n,f1,f2;
Matrix P = {0,0,0,
            0,0,0,
            0,0,0,
           };//这个是更具你自己构造出来的矩阵

Matrix I = {0,0,0,
            0,0,0,
            0,0,0,
           };//这是初始状态的矩阵

Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
{
    LL i,j,k;
    Matrix c;
    for (i = 0 ; i < MAX; i++)
        for (j = 0; j < MAX; j++)
        {
            c.m[i][j] = 0;
            for (k = 0; k < MAX; k++)
                c.m[i][j] += (a.m[i][k] * b.m[k][j])%mod;
            c.m[i][j] =  (c.m[i][j] + mod)%mod;
        }
    return c;
}

Matrix quickpow(int n)
{
    Matrix m = P, b = I;
    while (n >= 1)
    {
        if (n & 1)
            b = matrixmul(b,m);
        n = n >> 1;
        m = matrixmul(m,m);
    }
    return b;
}

附上模板题目:

描述

给你一个递推公式：

f(x)=a*f(x-2)+b*f(x-1)+c

并给你f(1),f(2)的值，请求出f(n)的值，由于f(n)的值可能过大，求出f(n)对1000007取模后的值。

注意:-1对3取模后等于2

输入

第一行是一个整数T,表示测试数据的组数(T<=10000)
随后每行有六个整数，分别表示f(1),f(2),a,b,c,n的值。
其中0<=f(1),f(2)<100,-100<=a,b,c<=100,1<=n<=100000000 (10^9)

输出

输出f(n)对1000007取模后的值

样例输入

2
1 1 1 1 0 5
1 1 -1 -10 -100 3

样例输出

5
999896

我们的目的是要找到一个矩阵可以实现这个递推关系，于是就是要找这样一个矩阵A使得：

这个矩阵实际上也是很好找到的，A=

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL MAX = 3;
const LL mod = 1000007;

typedef  struct
{
    LL  m[MAX][MAX];
}  Matrix;
LL a,b,c,n,f1,f2;
Matrix P = {0,0,0,
            1,0,0,
            0,1,1,
           };

Matrix I = {0,0,0,
            0,0,0,
            0,0,0,
           };

Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
{
    LL i,j,k;
    Matrix c;
    for (i = 0 ; i < MAX; i++)
        for (j = 0; j < MAX; j++)
        {
            c.m[i][j] = 0;
            for (k = 0; k < MAX; k++)
                c.m[i][j] += (a.m[i][k] * b.m[k][j])%mod;
            c.m[i][j] =  (c.m[i][j] + mod)%mod;
        }
    return c;
}

Matrix quickpow(int n)
{
    Matrix m = P, b = I;
    while (n >= 1)
    {
        if (n & 1)
            b = matrixmul(b,m);
        n = n >> 1;
        m = matrixmul(m,m);
    }
    return b;
}


int main()
{
#ifdef xxz
    freopen("in.txt","r",stdin);
#endif
    LL T;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld%lld%lld",&f1,&f2,&a,&b,&c,&n);
        P.m[0][1] = a, P.m[1][1] = b;
        I.m[0][0] = f1,I.m[0][1] = f2, I.m[0][2] = c;
        if(n == 1) printf("%lld\n",f1%mod%mod);
        else if(n == 2) printf("%d\n",f2%mod);
        else {

            Matrix temp = quickpow(n-2);
            if(temp.m[0][1]%mod >= 0) printf("%lld\n",(temp.m[0][1]%mod + mod)%mod);
            else printf("%lld\n",(temp.m[0][1]%mod + mod)%mod);

        }

    }

    return 0;
}

矩阵快速幂

原文：http://blog.csdn.net/u013445530/article/details/41877713