hdu: Count（矩阵快速幂）

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=10^4,n<=10^18

Output
共T行,每行一个正整数表示所求的答案

输入样例

5
3
6
9
12
15

输出样例

31
700
7486
64651
527023

带次方项的矩阵快速幂，利用二项式定理找寻n^x于(n-1)^xi的关系
可以采用写unit的方式给ans赋初始值
附ac代码

#include<bits/stdc++.h>
using namespace std;
const int N=6,mod=123456789;
int unit[N][N]={{1,2,1,3,3,1},{1,0,0,0,0,0},{0,0,1,3,3,1},{0,0,0,1,2,1},
{0,0,0,0,1,1},{0,0,0,0,0,1}};
typedef long long ll;
struct matrix{
    ll ma[N][N];
};
matrix muti(matrix a,matrix b)
{
    matrix c;
    for(int i=0;i<N;++i)
      for(int j=0;j<N;++j)
      c.ma[i][j]=0;
    for(int i=0;i<N;++i)
      for(int j=0;j<N;++j)
        for(int z=0;z<N;++z)
        {c.ma[i][j]+=(a.ma[i][z]%mod*(b.ma[z][j]%mod))%mod;
        c.ma[i][j]%=mod;
        }
    return c;
}
matrix pow_ma(matrix a,ll k)
{
    if(k==1) return a;
    matrix s;
    s=pow_ma(muti(a,a),k/2);
    if(k%2) s=muti(s,a);
    return s;
}
int main()
{
    int T;
    ll n;
    cin>>T;
    int b[N]={2,1,8,4,2,1};
    while(T--)
    {
        scanf("%lld",&n);
        matrix ans;
        for(int i=0;i<N;++i)
          for(int j=0;j<N;++j)
          ans.ma[i][j]=unit[i][j];
        ans=pow_ma(ans,n-2);
        ll sum=0;
        for(int i=0;i<N;++i)
        {
            sum+=b[i]*ans.ma[0][i]%mod;
        }
        printf("%lld\n",sum%mod);
    }
    return 0;
}