题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6470
Count
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 661 Accepted Submission(s): 258
Problem Description
Farmer John有n头奶牛.
某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:
第一头奶牛为1号,第二头奶牛为2号,第三头奶牛之后,假如当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.
现在Farmer John想知道,第n头奶牛的编号是多少,估计答案会很大,你只要输出答案对于123456789取模.

Input
第一行输入一个T,表示有T组样例
接下来T行,每行有一个正整数n,表示有n头奶牛 (n>=3)
其中，T=104,n<=1018
Output
共T行,每行一个正整数表示所求的答案
Sample Input
5
3
6
9
12
15
Sample Output
31
700
7486
64651
527023

这道题比赛时超时，请教学长之后，就发现这种题也是很有意思的；
那现在我先来解决怎么堆出矩阵快速幂，首先就是要知道矩阵是什么，这个知识我就跳过。
我们有题意推出一个公式：F[n]=F[n-1]+2F[n-2]+nnn;
那么我们运用矩阵：
A =[F[n-1] F[n-2] n^3 nn n 1];
然后在建一个矩阵
B=
1 1 0 0 0 0
2 0 0 0 0 0
1 0 1 0 0 0
0 0 3 1 0 0
0 0 3 2 1 0
0 0 1 1 1 0
AB，根据矩阵相乘可以得
C=
[F[n] F[n-1] (n+1)^3 (n+1)(n+1) (n+1) 2]
…
我们再利用快速幂得模板进行运算

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=123456789;
const int NN=6;
struct gg
{
    ll mm[NN][NN];
};
gg mmll(gg a,gg b)//模拟矩阵乘法
{
    gg ans;
    for(int i=0;i<NN;i++)
    {
        for(int j=0;j<NN;j++)
        {
            ans.mm[i][j]=0;//初始化矩阵
            for(int k=0;k<NN;k++)
            {
                ans.mm[i][j]+=a.mm[i][k]*b.mm[k][j]%mod;//矩阵相乘，a的行乘以b的列，得到ans行
                ans.mm[i][j]%=mod;//
            }
        }
    }
    return ans;
}
gg qiupow(gg a,ll b)
{
    gg ans;
    for(int i=0;i<NN;i++)//初始化矩阵：根据所学的线性代数的知识可以知道，单位矩阵就是初始的矩阵；所以，我们初始化要注意一下；
        for(int j=0;j<NN;j++)
            ans.mm[i][j]=0;
            for(int i=0;i<NN;i++)//单位矩阵
                ans.mm[i][i]=1;
    while(b)//矩阵快速幂
    {
        if(b&1)
        ans=mmll(ans,a);
        a=mmll(a,a);
        b/=2;
    }
    return ans;
}
int A[]={2,1,27,9,3,1};//A的值
int main()
{
    gg B;//矩阵B；
    B.mm[0][0]=1;B.mm[0][1]=1;B.mm[0][2]=0;B.mm[0][3]=0; B.mm[0][4]=0;B.mm[0][5]=0;
    B.mm[1][0]=2;B.mm[1][1]=0;B.mm[1][2]=0;B.mm[1][3]=0; B.mm[1][4]=0;B.mm[1][5]=0;
    B.mm[2][0]=1;B.mm[2][1]=0;B.mm[2][2]=1;B.mm[2][3]=0; B.mm[2][4]=0;B.mm[2][5]=0;
    B.mm[3][0]=0;B.mm[3][1]=0;B.mm[3][2]=3;B.mm[3][3]=1; B.mm[3][4]=0;B.mm[3][5]=0;
    B.mm[4][0]=0;B.mm[4][1]=0;B.mm[4][2]=3;B.mm[4][3]=2; B.mm[4][4]=1;B.mm[4][5]=0;
    B.mm[5][0]=0;B.mm[5][1]=0;B.mm[5][2]=1;B.mm[5][3]=1; B.mm[5][4]=1;B.mm[5][5]=1;
    ll t,n;
    scanf("%lld",&t);
    while(t--)
    {
        int a=0;
        scanf("%lld",&n);
        gg as=qiupow(B,n-2);//B的n-2次幂；
        if(n==1)
        {
            printf("1\n");
            continue;
        }
        if(n==2)
        {
            printf("2\n");
            continue;
        }
        for(int i=0;i<NN;i++)
        {
            a+=(A[i]*as.mm[i][0])%mod;//
        }
        printf("%lld\n",a%mod);
    }
    return 0;
}