Fzu 2198 快来快来数一数【矩阵快速幂】

 Problem 2198 快来快来数一数

Accept: 218    Submit: 704 Time Limit: 1000 mSec    Memory Limit : 65536 KB

 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

2 2 12345678987654321

 Sample Output

4 1733521876

 Source

FOJ有奖月赛-2015年10月

思路：

暴力打表得到四项，6 35 204 1189.

不难看出，F【i】=F【i-1】*6-F【i-2】；

那么构造矩阵为：

然后跑矩阵快速幂即可。

然而直接跑会TLE，在网上题解找到了一种优化常数的方法（极限数据其实还是会卡掉这种做法的。）

先预处理出64个乘方矩阵，然后对于n来讲，如果某一位为1的时候再向上乘一个乘方矩阵。

Ac代码：

#include<stdio.h> #include<iostream> #include<string.h> using namespace std; #define ll __int64 typedef struct Matrix { ll mat[3][3]; }matrix; ll mod=1e9+7; matrix A,B,Tmp[75]; Matrix matrix_mul(matrix a,matrix b) { matrix c; memset(c.mat,0,sizeof(c.mat)); int i,j,k; for(int i=0;i<3;i++) { for(int k=0;k<3;k++) { if(a.mat[i][k]==0)continue; for(int j=0;j<3;j++) { c.mat[i][j]=(c.mat[i][j]+((a.mat[i][k]*b.mat[k][j]))+mod)%mod; } } } return c; } Matrix matrix_quick_power(matrix a,ll k) { matrix b; memset(b.mat,0,sizeof(b.mat)); for(int i=0;i<3;i++) b.mat[i][i]=1;//单位矩阵b while(k) { if(k&1) { b=matrix_mul(a,b); k-=1; } else { a=matrix_mul(a,a); k/=2; } } return b; } void init() { A.mat[0][0]=6;A.mat[0][1]=-1;A.mat[0][2]=0; A.mat[1][0]=1;A.mat[1][1]=0;A.mat[1][2]=0; A.mat[2][0]=6;A.mat[2][1]=-1;A.mat[2][2]=1; Tmp[1]=A; for(int i=2;i<=64;i++) { Tmp[i]=matrix_mul(Tmp[i-1],Tmp[i-1]); } } int main() { int t; init(); scanf("%d",&t); while(t--) { ll n; scanf("%I64d",&n); memset(B.mat,0,sizeof(B.mat)); for(int i=0;i<3;i++)B.mat[i][i]=1; int i=1; while(n) { if(n&1) { B=matrix_mul(B,Tmp[i]); } n/=2; i++; } printf("%I64d\n",(B.mat[2][0]+mod)%mod); } return 0; }