## 【矩阵快速幂】nth Term LightOJ – 1096

You have to find the nth term of the following function:

f(n) = a * f(n-1) + b * f(n-3) + c, if(n > 2)

= 0, if(n ≤ 2)

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

Each case contains four integers n (0 ≤ n ≤ 108), a b c (1 ≤ a, b, c ≤ 10000).

Output
For each case, print the case number and f(n) modulo 10007.

Sample Input
2

10 1 2 3

5 1 3 9

Sample Output
Case 1: 162

Case 2: 27

a 0 b c        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 0 1           1             1

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace std;

struct mt{
int mmt[10][10];
}ans,res;
int t,hn,ha,hb,hc;
mt mul(mt a,mt b,int n)
{
mt tmp;
memset(tmp.mmt,0,sizeof(tmp.mmt));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
tmp.mmt[i][j]+=a.mmt[i][k]*b.mmt[k][j];
tmp.mmt[i][j]%=10007;
}
}
}
return tmp;
}
void mtqkpow(int a,int n)
{
for(int i=1;i<=n;i++) ans.mmt[i][i]=1;
while(a)
{
if(a&1) ans=mul(ans,res,n);
res=mul(res,res,n);
a>>=1;
}
}
int main()
{
cin>>t;
for(int i=1;i<=t;i++)
{
memset(ans.mmt,0,sizeof(ans.mmt));
memset(res.mmt,0,sizeof(res.mmt));
scanf("%d%d%d%d",&hn,&ha,&hb,&hc);
if(hn<=2){
printf("Case %d: 0\n",i);
continue;
}
res.mmt[1][1]=ha;
res.mmt[1][3]=hb;
res.mmt[1][4]=hc;
res.mmt[2][1]=1;
res.mmt[3][2]=1;
res.mmt[4][4]=1;
mtqkpow(hn-1,4);
mt m;
memset(m.mmt,0,sizeof(m.mmt));
m.mmt[1][1]=hc;
m.mmt[4][1]=1;
int anser=0;
for(int k=1;k<=4;k++)
{
anser+=ans.mmt[3][k]*m.mmt[k][1];
anser%=10007;
}
printf("Case %d: %d\n",i,anser);
}
}