矩阵连乘。

1.求具体值矩阵连乘1确定递推公式和我们要求什么2将我们要求的东西用前项表示出来用到的元素就是状态矩阵3元素之间的递推关系组成转移矩阵2.求后n项对值取模1en)即可3.求位数通项公式log1014.求前n项tplog10(1.0/sqrt(5))(double)n*log10((1.0sqrt(5))/2.0);anspow(10,tp-(int)tpn-1);5.找规律通项公式的推导#includebits/stdc.h using namespace std; int main() { long long n,a,b,u,v; while(scanf(%lld %lld %lld %lld %lld,n,a,b,u,v)!EOF) { double csqrt(u*u4*v); double x(uc)/2.0; double y(u-c)/2.0; double lenn*log10(x)log10(b-a*y)-log10(c); printf(%lld\n,(long long)len1); } return 0; }比较麻烦思路清晰的#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x typedef long long ll; typedef pairint,int PII; const int MAX52; ll f1,f2,a,b,k,n,MOD,dim; struct Matrix{ ll m[MAX][MAX]; Matrix(bool ident false){ memset(m,0,sizeof(m)); if(ident){ for(int i0;iMAX;i) m[i][i]1; } } }; Matrix I(true); Matrix P; Matrix mul(Matrix a,Matrix b) { Matrix c; for(int i0;iMAX;i){ for(int j0;jMAX;j){ for(int k0;kMAX;k){ c.m[i][j]a.m[i][k]*b.m[k][j]%MOD; c.m[i][j]%MOD; } } } return c; } Matrix qpow(Matrix base,ll exp) { Matrix res(true); while(exp){ if(exp1) resmul(res,base); basemul(base,base); exp1; } return res; } ll mod_pow(ll x,ll e){ ll res1; x%MOD; while(e){ if(e1) resres*x%MOD; xx*x%MOD; e1; } return res; } void solve() { cinf1f2abknMOD; if(MOD1){ cout0endl; return; } if(k0){ cout(n%MOD)endl; return; } if(n1){ coutmod_pow(f1,k)endl; return ; } dimk2; vectorvectorll C(k1,vectorll(k1,0)); for(int i0;ik;i){ C[i][0]C[i][i]1%MOD; for(int j1;ji;j){ C[i][j](C[i-1][j-1]C[i-1][j])%MOD; } } vectorllpowA(k1,1),powB(k1,1); for(int i1;ik;i){ powA[i]powA[i-1]*(a%MOD)%MOD; powB[i]powB[i-1]*(b%MOD)%MOD; } Matrix M; for(int i0;ik;i){ for(int j0;jk;j){ if(ijk){ int tk-i-j; ll coeffC[k-i][j]; coeffcoeff*powA[t]%MOD; coeffcoeff*powB[j]%MOD; M.m[i][j]coeff; } } } Matrix B; for(int i0;ik;i){ for(int j0;jk;j){ B.m[i][j]M.m[i][j]; } } B.m[k1][0]1; B.m[k1][k1]1; vectorllpowF1(k1,1),powF2(k1,1); for(int i1;ik;i){ powF1[i]powF1[i-1]*(f1%MOD)%MOD; powF2[i]powF2[i-1]*(f2%MOD)%MOD; } vectorllV2(dim,0); for(int i0;ik;i){ V2[i]powF2[k-i]*powF1[i]%MOD; } V2[k1]powF1[k]; Matrix Pnqpow(B,n-2); vectorllVn(dim,0); for(int i0;idim;i){ for(int j0;jdim;j){ Vn[i](Vn[i]Pn.m[i][j]*V2[j])%MOD; } } ll ans(Vn[dim-1]Vn[0])%MOD; coutansendl; } int main() { IOS int T1;cinT; while(T--) solve(); return 0; }#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x typedef long long ll; typedef pairint,int PII; const int N1005; const int MOD10000; const int MAX2; typedef struct{ ll m[MAX][MAX]; } Matrix; Matrix P{0,1, 1,1}; Matrix I{1,0, 0,1}; ll n; ll a[40]; void Init(){ a[2]a[1]1;a[0]0; for(int i3;i39;i){ a[i]a[i-1]a[i-2]; } } Matrix matrixmul(Matrix a,Matrix b) { Matrix c; for(int i0;iMAX;i){ for(int j0;jMAX;j){ c.m[i][j]0; for(int k0;kMAX;k){ c.m[i][j](a.m[i][k]*b.m[k][j])%MOD; c.m[i][j]%MOD; } } } return c; } Matrix qpow(ll n){ Matrix mP,bI; while(n1){ if(n1){ bmatrixmul(b,m); } nn1; mmatrixmul(m,m); } return b; } void solve() { Init(); while(cinn){ if(n39){ couta[n]endl; continue; } Matrix tmpqpow(n); int ans_etmp.m[0][1]%MOD; double log_tplog10(1.0/sqrt(5))(double)n*log10((1.0sqrt(5))/2.0); int ans_s(int)pow(10,log_tp-(int)log_tp3); coutans_s...; printf(%04d\n,ans_e); } } int main() { int T1;//cinT; while(T--) solve(); return 0; }