http://www.cnblogs.com/frog112111/archive/2013/05/19/3087648.html
知道递推式怎么去构造矩阵，这篇博文说的很清楚

image.png

一个新操作
如 f(n) = 2f(n-1) - 5f(n-2) + 4f(n-4)
那么可以构建矩阵
| 2 -5 0 4 | | f(n-1) | | f(n) |
| 1 0 0 0 | * | f(n-2) | = | f(n-1) |
| 0 1 0 0 | | f(n-3) | | f(n-2) |
| 0 0 1 0 | | f(n-4) | | f(n-3) |

第一排写系数
左下角的(n-1)*(n-1) 的矩阵主对角线上填1
嗯，就是这个操作，只要有递推式分分钟弄出来
Float-Bonacci
TengBieBie已经学习了很多关于斐波那切数列的性质，所以他感到一些些厌烦。现在他遇到了一个新的数列，这个数列叫做Float-Bonacci。这里有一个关于Float-Bonacci的定义。

对于一个具体的n，TengBieBie想要快速计算FB(n).
但是TengBieBie对FB的了解非常少，所以他向你求助。
你的任务是计算FB(n).FB(n)可能非常大，请输出FB(n)%1,000,000,007
(1e9+7)即可。
Input
输入共一行，在一行中给出一个整数n (1<=n<=1,000,000,000)。
Output
对于每一个n，在一行中输出FB(n)%1,000,000,007 (1e9+7)。
Sample Input
5
Sample Output
2

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<string.h>
#define LL long long 
using namespace std;
const int mod = 1e9 + 7;
struct mat
{
    LL m[35][35];
}unit;

LL n;
void init_unit()
{
    for(int i=1;i<=34;i++)
    {
        for(int j=1;j<=34;j++)
        {
            if(i==j)
            {
                unit.m[i][j] = 1;
            }
        }
    }
 } 
 
mat operator * (mat a, mat b)
{
    mat ret;
    LL x;
    for(int i=1;i<=34;i++)
    {
        for(int j=1;j<=34;j++)
        {
            x = 0;
            for(int k=1;k<=34;k++)
            {
                x += ((LL)a.m[i][k] * b.m[k][j])%mod;
                ret.m[i][j] = x%mod;
            }
        }
    }
    return ret;
}
mat pow_mat(mat a, LL x)
{
    mat ret = unit;
    while(x)
    {
        if(x & 1) ret = ret*a;
        a = a*a;
        x >>= 1;
    }
    return ret;
}

int main()
{
    scanf("%lld",&n);
    mat a;
    memset(a.m,0,sizeof(a.m));
    init_unit();
    a.m[1][10] = a.m[1][34] = 1;
    for(int i=2;i<=34;i++)
    {
        a.m[i][i-1] = 1;
    } 
     //print(a);
     if(n<=4)
     {
        printf("1\n");
     }
     else
     {
        LL x = (n-4)*10;
        mat res = pow_mat(a,x);
        LL ans = 0;
        //print(res);
        for(int i=1;i<=34;i++)
        {
            ans = ( ans + res.m[1][i] ) %mod;
            //printf("ans = %d\n",ans);
         }
         //print(res);
         printf("%lld\n",ans);
     }
}