51nod-1358-浮波那契（构造矩阵）

TengBieBie已经学习了很多关于斐波那切数列的性质，所以他感到一些些厌烦。现在他遇到了一个新的数列，这个数列叫做Float-Bonacci。这里有一个关于Float-Bonacci的定义。

对于一个具体的n，TengBieBie想要快速计算FB(n).

但是TengBieBie对FB的了解非常少，所以他向你求助。

你的任务是计算FB(n).FB(n)可能非常大，请输出FB(n)%1,000,000,007 (1e9+7)即可。

输入共一行，在一行中给出一个整数n (1<=n<=1,000,000,000)。Output
对于每一个n，在一行中输出FB(n)%1,000,000,007 (1e9+7)。Input示例
5Output示例
2System Message (题目提供者)和正常的fib不同，这里的n-3.4项并不是整数项，因此很自然的想到需要一种转换，使得递推公式的前两项变成整数项，这里可以采用乘10操作来构造一种新的fib数列则递推式将变成：    f（n）=f（n-10）+f（n-34）其中的f（n）对应fib里的fib（n/10）剩下的就是单位矩阵的构造了。如找到f(n) = 4f(n - 1) - 3f(n - 2) + 2f(n - 4)的第k项。 矩阵构造为： ，这里采用每行向下移一位，最后一行移到第1行
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define Mod 1000000007typedef long long ll;struct node{	ll a[40][40];};node work1(node x,node y){	node tmp;	int i,j,k;	for(i=1;i<=34;i++)		for(j=1;j<=34;j++)		{			tmp.a[i][j]=0;			for(k=1;k<=34;k++)				tmp.a[i][j]+=(x.a[i][k]*y.a[k][j])%Mod;			tmp.a[i][j]%=Mod;		}	return tmp;}node work(node x,ll y){	node res;	for(int i=1;i<=34;i++)		for(int j=1;j<=34;j++)		{			if(i==j)				res.a[i][j]=1;			else				res.a[i][j]=0;		}	while(y)	{		if(y%2)			res=work1(res,x);		x=work1(x,x);		y/=2;	}	return res;}int  main(){	ll n,i,j,x;	node t;	for(i=1;i<=34;i++)		for(j=1;j<=34;j++)			t.a[i][j]=0;	scanf("%lld",&n);	if(n<=4)	{		PRintf("1/n");		return 0;	}	x=(n-4)*10;	for(i=2;i<=34;i++)		t.a[i][i-1]=1;	t.a[1][10]=t.a[1][34]=1;	node res=work(t,x);	ll ans=0;	for(i=1;i<=34;i++)		ans=(ans+res.a[1][i])%Mod;	printf("%lld/n",ans);}