递推式：
a0 = A0 ai = ai-1*AX+AY b0 = B0 bi = bi-1*BX+BY(AX,AY,BX,BY均为已知数字)求 0-n-1 的 ai*bi 的和(设为 Sn 吧)线性代数只能做线性变换，故要得出 ai*bi 的递推式 ai*bi = AXBX*ai-1*bi-1 + AXBY*ai-1 + BXAY*bi-1 + AYBY然后写成矩阵|1 AXBX AXBY BXAY AYBY| | Sn-1 | | Sn ||0 AXBX AXBY BXAY AYBY| | an-1*bn-1| |an*bn||0 0 AX 0 AY | * | an-1 | = | an ||0 0 0 BX BY | | bn-1 | | bn ||0 0 0 0 1 | | 1 | | 1 |最后用 快速幂 运算。1 #include2 #include 3 #include 4 using namespace std; 5 #define LL long long 6 const LL mod = 1000000007; 7 struct P{ LL a[6][6]; }; 8 LL ans,n; 9 LL a0,ax,ay,b0,bx,by;10 P s,c;11 int i,j;12 P mult(const P& a,const P& b)13 {14 P c;15 for(i=1;i<=5;++i)16 for(j=1;j<=5;++j)17 {18 c.a[i][j]=0;19 for(int k=1;k<=5;k++)20 c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j] )%mod;21 }22 return c;23 }24 void ini()25 {26 for(i=1;i<=5;++i)27 for(j=1;j<=5;++j)28 c.a[i][j]=s.a[i][j]=0;29 s.a[1][1]=1; s.a[1][2]=ax*bx%mod; s.a[1][3]=ax*by%mod; s.a[1][4]=bx*ay%mod; s.a[1][5]=ay*by%mod;30 s.a[2][2]=ax*bx%mod; s.a[2][3]=ax*by%mod; s.a[2][4]=bx*ay%mod; s.a[2][5]=ay*by%mod;31 s.a[3][3]=ax; s.a[3][5]=ay; 32 s.a[4][4]=bx; s.a[4][5]=by;33 s.a[5][5]=1;34 }35 void fuc(LL n)36 {37 for(int i=1;i<=5;i++) c.a[i][i]=1;38 while(n)39 {40 if(n&1) c=mult(c,s);41 s=mult(s,s);42 n>>=1;43 }44 }45 int main()46 {47 while(~scanf("%lld",&n))48 {49 scanf("%lld%lld%lld %lld%lld%lld",&a0,&ax,&ay,&b0,&bx,&by); 50 if(n==0)51 {52 puts("0"); continue;53 }54 a0%=mod; b0%=mod; ax%=mod; bx%=mod; ay%=mod; by%=mod;55 ini();56 fuc(n-1);57 ans=a0*b0%mod*c.a[1][1]%mod;58 ans=(ans+c.a[1][2]*a0%mod*b0%mod)%mod;59 ans=(ans+a0*c.a[1][3]%mod)%mod;60 ans=(ans+b0*c.a[1][4]%mod)%mod;61 ans=(ans+c.a[1][5]%mod)%mod;62 printf("%lld\n",ans);63 }64 }