递推时把 (n+1)^3 拆开 构造矩阵即可
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define mod 123456789
- struct Mat{
- ll m[10][10];
- Mat(){memset(m,0,sizeof m);}
- }A;
- ll n,F[13];
- void mul(Mat A,ll F[13]){
- ll B[13]={};
- for(int i=0;i<6;i++)
- for(int j=0;j<6;j++)
- B[i]=(B[i]+A.m[i][j]*F[j]%mod)%mod;
- memcpy(F,B,sizeof B);
- }
- void mulself(Mat & A,Mat B){
- Mat C;
- for(int i=0;i<6;i++)
- for(int j=0;j<6;j++)
- for(int k=0;k<6;k++)
- C.m[i][j]=(C.m[i][j]+A.m[i][k]*B.m[k][j]%mod)%mod;
- memcpy(A.m,C.m,sizeof C.m);
- }
- int main(){
- int T;
- cin>>T;
- while(T--){
- F[0]=2,F[1]=1,F[2]=27,F[3]=9,F[4]=3,F[5]=1;
- memset(A.m,0,sizeof A.m);
- A.m[1][0]=1;
- A.m[0][0]=1;A.m[0][1]=2;A.m[0][2]=1;
- A.m[2][2]=1;A.m[2][3]=3;A.m[2][4]=3;A.m[2][5]=1;
- A.m[3][3]=1;A.m[3][4]=2;A.m[3][5]=1;
- A.m[4][4]=1;A.m[4][5]=1;
- A.m[5][5]=1;
- cin>>n;
- n-=2;
- while(n){
- if(n%2)
- mul(A,F);
- mulself(A,A);
- n>>=1;
- }
- cout<<F[0]%mod<<'\n';
- }
- }
来源: http://www.bubuko.com/infodetail-2992170.html