这里有一份解题报告
这是理论知识：
最主要的是构造乘法矩阵，这个是通过递推关系得到的。
有了它，求数列的第n项可以在log(n)的时间里求出来。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include<vector> 8 #define maxn 1010 9 #define mod 1000000007 10 using namespace std; 11 typedef long long ll; 12 struct Matrix{ 13 ll a[10][10]; 14 }res,A,F,ans,temp; 15 Matrix mul(Matrix a,Matrix b){ 16 memset(temp.a,0,sizeof(temp.a)); 17 for(int i=0;i<5;++i){ 18 for(int j=0;j<5;++j){ 19 for(int k=0;k<5;++k){ 20 temp.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod; 21 temp.a[i][j]%=mod; 22 } 23 } 24 } 25 return temp; 26 } 27 void quick_pow(ll k){ 28 memset(res.a,0,sizeof(res.a)); 29 for(int i=0;i<5;++i)res.a[i][i]=1; 30 while(k){ 31 if(k&1)res = mul(res,A); 32 A = mul(A,A); 33 k>>=1; 34 } 35 } 36 int main (){ 37 ll a0,ax,ay; 38 ll b0,bx,by; 39 ll n; 40 ll f1,a1,b1,s0; 41 while(cin>>n){ 42 cin>>a0>>ax>>ay; 43 cin>>b0>>bx>>by; 44 if(n==0){printf("0 ");continue;} 45 a1 = ((a0*ax)%mod+ay)%mod; 46 b1 = ((b0*bx)%mod+by)%mod; 47 f1 = (a1*b1)%mod; 48 s0 = (a0*b0)%mod; 49 memset(A.a,0,sizeof(A.a)); 50 A.a[0][0]=(ax*bx)%mod; 51 A.a[1][0]=(ax*by)%mod; 52 A.a[2][0]=(ay*bx)%mod; 53 A.a[3][0]=(ay*by)%mod; 54 A.a[1][1]=ax%mod; 55 A.a[3][1]=ay%mod; 56 A.a[2][2]=bx%mod; 57 A.a[3][2]=by%mod; 58 A.a[3][3]=1; 59 A.a[0][4]=1; 60 A.a[4][4]=1; 61 memset(F.a,0,sizeof(F.a)); 62 F.a[0][0]=f1%mod; 63 F.a[0][1]=a1%mod; 64 F.a[0][2]=b1%mod; 65 F.a[0][3]=1; 66 F.a[0][4]=s0%mod; 67 quick_pow(n-1); 68 ans=mul(F,res); 69 printf("%lld ",(ans.a[0][4])%mod); 70 } 71 return 0; 72 }
PS：杭电不支持long long lld 输出，(╯‵□′)╯︵┻━┻