矩阵快速幂裸题，不过听说好像循环就能过，=_=……蒙蔽的我。。。。

1.问题描述

Given a code (not optimized), and necessary inputs, you have to find the output of the code for the inputs. The code is as follows:

int a, b, c, d, e, f; int fn( int n ) {     if( n == 0 ) return a;     if( n == 1 ) return b;     if( n == 2 ) return c;     if( n == 3 ) return d;     if( n == 4 ) return e;     if( n == 5 ) return f;     return( fn(n-1) + fn(n-2) + fn(n-3) + fn(n-4) + fn(n-5) + fn(n-6) ); } int main() {     int n, caseno = 0, cases;     scanf("%d", &cases);     while( cases-- ) {         scanf("%d %d %d %d %d %d %d", &a, &b, &c, &d, &e, &f, &n);         printf("Case %d: %d\n", ++caseno, fn(n) % 10000007);     }     return 0; }

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains seven integers, a, b, c, d, e, f and n. All integers will be non-negative and 0 ≤ n ≤ 10000 and the each of the others will be fit into a 32-bit integer.

Output

For each case, print the output of the given code. The given code may have integer overflow problem in the compiler, so be careful.

2 解释

意思就是，f(n)=f(n-1)+....+f(n-5); 以下是AC代码

3 代码

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> const long long mod=10000007; using namespace std; struct T{ long long mx[10][10]; int lenx,leny; T(){ memset(mx,0,sizeof(mx)); } void base(){ memset(mx,0,sizeof(mx)); mx[6][1]=mx[6][2]=mx[6][3]=mx[6][4]=mx[6][5]=mx[6][6]=1; mx[1][2]=mx[2][3]=mx[3][4]=mx[4][5]=mx[5][6]=1; } void print(){ for(int i=1;i<=lenx;i++){ for(int j=1;j<=leny;j++){ printf("%d ",mx[i][j]); } printf("\n"); } } void get_mx(){ memset(mx,0,sizeof(mx)); for(int i=1;i<=7;i++)mx[i][i]=1; } }; T operator*(T x,T y){ T res; res.lenx=x.lenx; res.leny=y.leny; for(int i=1;i<=res.lenx;i++){ for(int j=1;j<=res.leny;j++){ for(int k=1;k<=x.leny;k++){ res.mx[i][j]=(res.mx[i][j]+(x.mx[i][k]*y.mx[k][j])%mod)%mod; } } } return res; } T qpow(T x,int y){ T res; res.get_mx(); res.lenx=x.lenx,res.leny=x.leny; while(y){ if(y&1)res=res*x; x=x*x; y>>=1; } return res; } int main(){ int i,j,k,m,n; int a,b,c,d,e,f; int Case; scanf("%d",&Case); for(i=1;i<=Case;i++){ scanf("%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&n); if(n==0)printf("Case %d: %d\n",i,a%mod); else if(n==1)printf("Case %d: %d\n",i,b%mod); else if(n==2)printf("Case %d: %d\n",i,c%mod); else if(n==3)printf("Case %d: %d\n",i,d%mod); else if(n==4)printf("Case %d: %d\n",i,e%mod); else if(n==5)printf("Case %d: %d\n",i,f%mod); else{ T ans; ans.base(); ans.lenx=6,ans.leny=6; ans=qpow(ans,n-5); T res; res.lenx=6,res.leny=1; res.mx[1][1]=a; res.mx[2][1]=b; res.mx[3][1]=c; res.mx[4][1]=d; res.mx[5][1]=e; res.mx[6][1]=f; res=ans*res; printf("Case %d: %lld\n",i,res.mx[6][1]); } } return 0; }