题目传送门：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): 301 Accepted Submission(s): 127
Problem Description
Farmer John有n头奶牛.
某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:
第一头奶牛为1号,第二头奶牛为2号,第三头奶牛之后,假如当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.
现在Farmer John想知道,第n头奶牛的编号是多少,估计答案会很大,你只要输出答案对于123456789取模.
某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:
第一头奶牛为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
接下来T行,每行有一个正整数n,表示有n头奶牛 (n>=3)
其中，T=10^4,n<=10^18
Output
共T行,每行一个正整数表示所求的答案
Sample Input
5
3
6
9
12
15
Sample Output
31
700
7486
64651
527023
Source
解题思路：
很裸的一道矩阵快速幂的题，递推式都给出来了。
问题在于如何构造转移矩阵？也就是如何搞定 n 的3次方？
最终的转移矩阵：
AC code：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MAXN = ;
const LL MOD = ;
template<typename T, int N = >
struct Matrix
{
Matrix(int f = ):n(sizeof(data[])/sizeof(data[][])){
for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
data[i][j] = ;
if(f)
for(int i = ; i < n; i++) data[i][i] = T();
} Matrix operator * (const Matrix other) const{
Matrix<T, N> ret;
for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
for(int k = ; k < n; k++)
ret.data[i][j] = (ret.data[i][j] + data[i][k] * other.data[k][j]%MOD)%MOD;
return ret;
} Matrix operator + (const Matrix other) const{
Matrix<T, N> ret;
for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
ret.data[i][j] = (data[i][j] + other[i][j])%MOD;
return ret;
} Matrix operator % (const LL MOD){
return *this;
} T data[N][N];
int n; }; template<typename T>
T mul(T a, LL n, LL mod)
{
T ret();
for(; n ; n >>= ){
ret = ret*(n& ? a:T()) %mod;
a = a*a%mod;
}
return ret;
} const LL modulu[MAXN][MAXN] = {
{, , , , , },
{, , , , , },
{, , , , , },
{, , , , , },
{, , , , , },
{, , , , , }
}; int main()
{
std::ios::sync_with_stdio(false);
int T;
cin >> T;
for(LL n; T--; ){
cin >> n;
if(n <= ){
cout << n << endl;
continue;
}
Matrix<LL, MAXN> a;
memcpy(a.data, modulu, sizeof(modulu));
a = mul(a, n-, MOD);
cout << (a.data[][]* + a.data[][]* + a.data[][]* + a.data[][]* + a.data[][]* + a.data[][]*)%MOD << endl;
}
return ;
}