HDU 4686 Arc of Dream（构造矩阵）_综合

题目链接：
HDU 4686 Arc of Dream
题意:
给出 $n,a0,ax,ay,b0,bx,by$ .且 $a[i]=ax*a[i-1]+ay,b[i]=bx*b[i-1]+by.$
定义 $f[n]=$ $\sum_{k=0}^p(a[k]*b[k])(其中p=n-1)$ .
求出 $n mod (1e9+7)$ .
分析；
构造矩阵。想要由

 * 1                    1* a[i-1]               a[i]* b[i-1]         得到  b[i]* a[i-1]*b[i-1]        a[i]*b[i]* f[i-1]               f[i]

1的出现是因为a[i]和b[i]的递推式中有常数项。
很容易得到矩阵

 *    1       0      0      0      0*    ay      ax     0      0      0* A =by      0      bx     0      0*    ay*by   ax*by  bx*ay  ax*bx  0*    ay*by   ax*by  bx*ay  ax*bx  1

然后用矩阵快速幂结局就行啦。
注意：
当 $n==0$ 时，结果是0.需要特判。我没注意，结果 $TLE$ 了三发，白白改了一个多小时， $too$ $naive，o(╯□╰)o$

//1580K 218MS
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const long long mod=(long long)(1e9+7);long long n,a0,ax,ay,b0,bx,by;struct Matrix{int row,col;long long data[10][10];
};inline void init(Matrix& x)
{x.row=x.col=5;memset(x.data,0,sizeof(x.data));x.data[1][1]=x.data[5][5]=1;x.data[2][1]=ay,x.data[2][2]=ax,x.data[3][1]=by,x.data[3][3]=bx;x.data[4][1]=x.data[5][1]=ay*by%mod,x.data[4][2]=x.data[5][2]=ax*by%mod;x.data[4][3]=x.data[5][3]=bx*ay%mod,x.data[4][4]=x.data[5][4]=ax*bx%mod;
}inline Matrix multiply(Matrix a,Matrix b)
{Matrix ans;ans.row=a.row,ans.col=b.col;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=ans.row;i++){for(int j=1;j<=ans.col;j++){for(int k=1;k<=a.col;k++){ans.data[i][j]+=a.data[i][k]*b.data[k][j];ans.data[i][j]%=mod;}}}return ans;
}inline Matrix quick_power(Matrix a,long long n)
{Matrix ans,tmp=a,pre;ans.row=ans.col=pre.row=pre.col=a.row;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=ans.row;i++)ans.data[i][i]=1;while(n){if(n&1){ans=multiply(ans,tmp);}tmp=multiply(tmp,tmp);n>>=1;}return ans;
}int main()
{freopen("Sin.txt","r",stdin);while(~scanf("%I64d",&n)){scanf("%I64d %I64d %I64d",&a0,&ax,&ay);scanf("%I64d %I64d %I64d",&b0,&bx,&by);a0%=mod,ax%=mod,ay%=mod;b0%=mod,bx%=mod,by%=mod;if(n==0){printf("0\n");continue;}Matrix ans,tmp;init(ans);ans=quick_power(ans,n-1);tmp.row=5,tmp.col=1;tmp.data[1][1]=1,tmp.data[2][1]=a0,tmp.data[3][1]=b0;tmp.data[4][1]=tmp.data[5][1]=a0*b0%mod;tmp=multiply(ans,tmp);printf("%I64d\n",tmp.data[5][1]%mod);} return 0;
}