奶牛的编号规则：当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.

第一头奶牛为1号,第二头奶牛为2号

第n头奶牛的编号是多少, 答案模123456789

 

题解：给你公式 

很明显这是一道矩阵快速幂的题目

f(n) = f(n-1) + f(n-2) + n^3

(n+1)^3 = n^3 + 3*n^2 +3*n + 1

推出的矩阵为

/*
Algorithm: 矩阵快速幂
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 123456789LL
#define line printf("--------------");
using namespace std;
struct node { //2维6阶矩阵
	ll mapp[7][7];
	void init() { //正对角线初始化为1 其他初始化为0
		memset(mapp, 0, sizeof(mapp));
		for(int i = 0; i < 7; i++) {
			mapp[i][i] = 1;
		}
	}
	void initall() { //全初始化为0
		memset(mapp, 0, sizeof(mapp));
	}
};
node mul(node aa, node bb) {//矩阵相乘
	node ans;
	ans.initall();
	for(int i = 0; i < 6; i++) {
		for(int j = 0; j < 6; j++) {
			for(int k = 0; k < 6; k++) {
				ans.mapp[i][j] += aa.mapp[i][k] * bb.mapp[k][j];
				ans.mapp[i][j] %= mod;
			}
		}
	}
	return ans;
}
node quickpownode(node aa, ll n) {//快速幂
	node ans;
	ans.init();//相当于数字1
	while(n) {
		if(n & 1) {
			ans = mul(aa, ans);
		}
		aa = mul(aa, aa);
		n/=2;
	}
	return ans;
}
int main() {
	ll n;
	/*
	1 1 0 0 0 0
	2 0 0 0 0 0
	1 0 1 0 0 0
	0 0 1 1 0 0
	0 0 1 2 1 0
	0 0 1 3 3 1
	*/
	node tmp;
	tmp.initall();
	tmp.mapp[0][0] =tmp.mapp[0][1] =tmp.mapp[2][0] =tmp.mapp[2][2]=tmp.mapp[3][2] =tmp.mapp[3][3] =tmp.mapp[4][2]=tmp.mapp[4][4] =tmp.mapp[5][2] =tmp.mapp[5][5] = 1;
	tmp.mapp[1][0] = tmp.mapp[4][3] = 2;
	tmp.mapp[5][3] = tmp.mapp[5][4] = 3;
	int t;
	cin>>t;
	while(t--) {
		cin>>n;
		node tt = quickpownode(tmp, n-2);
		node ans;
		ans.initall();
		/*
		2 1 n^3 3*n^2 n^2 1
		*/
		ans.mapp[0][0] = 2;
		ans.mapp[0][1] = 1;
		ans.mapp[0][2] = 3*3*3;
		ans.mapp[0][3] = 3*3*3;
		ans.mapp[0][4] = 3*3;
		ans.mapp[0][5] = 1;
		node as = mul(ans, tt);
		cout<<as.mapp[0][0]<<endl;
	}

	return 0;
}