Farmer John有n头奶牛.
某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:
第一头奶牛为1号,第二头奶牛为2号,第三头奶牛之后,假如当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.
现在Farmer John想知道,第n头奶牛的编号是多少,估计答案会很大,你只要输出答案对于123456789取模.
5
3
6
9
12
15
31 700 7486 64651 527023
https://www.cnblogs.com/zquzjx/p/10549775.html
#include <iostream> #include<cstdio> #include<cstring> #define mod 123456789 typedef long long ll; using namespace std; const int MAXN=10; struct Mat{ int n,m; ll mat[MAXN][MAXN]; Mat(){ memset(mat,0,sizeof(mat)); n=MAXN,m=MAXN; } Mat(int x,int y){ memset(mat,0,sizeof(mat)); n=x,m=y; }; Mat operator*(Mat b){ Mat c(n,b.m); for(int i=0;i<n;i++) for(int j=0;j<b.m;j++){ for(int k=0;k<m;k++){ c.mat[i][j]+=(mat[i][k]*b.mat[k][j])%mod; c.mat[i][j]%=mod; } } return c; } Mat operator+(Mat b){ Mat c(n,m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) c.mat[i][j]=(mat[i][j]+b.mat[i][j])%mod; return c; } void in(){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%lld",&mat[i][j]); } void out(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++) printf("%lld%c",mat[i][j],j==m-1?‘\n‘:‘ ‘); } } }ans(6,1),A(6,6),E(6,6); void init(){ A.mat[0][0]=1,A.mat[0][1]=2,A.mat[0][2]=1, A.mat[1][0]=1, A.mat[2][2]=1,A.mat[2][3]=3,A.mat[2][4]=3,A.mat[2][5]=1, A.mat[3][3]=1,A.mat[3][4]=2,A.mat[3][5]=1, A.mat[4][4]=1,A.mat[4][5]=1, A.mat[5][5]=1; ans.mat[0][0]=2,ans.mat[1][0]=1,ans.mat[2][0]=27,ans.mat[3][0]=9,ans.mat[4][0]=3,ans.mat[5][0]=1; E.mat[0][0]=1,E.mat[1][1]=1,E.mat[2][2]=1,E.mat[3][3]=1,E.mat[4][4]=1,E.mat[5][5]=1; } Mat qpow(Mat a,ll b){ Mat ret=E; while(b){ if(b&1) ret=ret*a; a=a*a; b>>=1; } return ret; } int main() { int t;scanf("%d",&t); while(t--){ ll n;scanf("%lld",&n); init(); ans=qpow(A,n-2)*ans; printf("%lld\n",ans.mat[0][0]); } return 0; }
原文：https://www.cnblogs.com/lllxq/p/10573364.html
