题目链接：HDU4686
题目大意：，就是计算这个公式。
思路：把这个公式拆成f(n)=f(n-1)+a 类似形式 最重要就是要把初始矩阵求出来
ai i代表下标 Sn 代表i=0~i=n-1的和
ai*bi=（ai-1*AX+AY）*（bi-1*BX+BY）=ai-1*bi-1*AX*BX+ai-1*AX*BY+bi-1*AY*BX+AY*BY 我们把这个公式的系数提出来
而 Sn=Sn-1+an*bn;
矩阵 （Sn an*bn an bn 1）T=5X5矩阵 *（Sn-1 an-1*bn-1 an-1 bn-1 1）;
5X5矩阵第一行 1 1 0 0 0
5X5矩阵第二行0 AX*BX AX*BY AY*BX AY*BY
5X5矩阵第三行0 0 AX 0 AY
5X5矩阵第四行 0 0 0 BX BY
5X5矩阵第五行 0 0 0 0 1
矩阵就是长这个样子。已经很努力的去对齐了- -
另外注意坑点，考虑到每一个数据都会很大，要用long long 并且出现乘积的地方都要取模，包括上述矩阵中出现乘积的地方，不然会wa很多次，不要问我是怎么知道的- -
还有一个特例就是 n=0 的时候，要输出0， 不然会TLE
下面附上AC代码：
/* 2017年8月5日15:26:51 H AC */ #include<stdio.h> #include<string.h> typedef long long ll; const int maxn=5; const ll mod=1e9+7; ll n,a0,ax,ay,b0,bx,by; typedef struct{ ll mat[maxn][maxn]; void init(){ memset(mat,0,sizeof(mat)); for(int i=0;i<maxn;i++){ mat[i][i]=1; } } }matrix; matrix multi(matrix a,matrix b) { matrix c; for(int i=0;i<maxn;i++) { for(int j=0;j<maxn;j++) { c.mat[i][j]=0; for(int k=0;k<maxn;k++) { c.mat[i][j]+=(a.mat[i][k] * b.mat[k][j])%mod; c.mat[i][j]%=mod; } } } return c; } matrix fast_mod(ll n,matrix p) { matrix ans,base=p; ans.init(); while(n) { if(n&1) ans=multi(ans,base); base=multi(base,base); n>>=1; } return ans; } int main(){ while(~scanf("%I64d",&n)){ scanf("%I64d%I64d%I64d",&a0,&ax,&ay); scanf("%I64d%I64d%I64d",&b0,&bx,&by); matrix p={1,1,0,0,0, 0,ax*bx%mod,ax*by%mod,ay*bx%mod,ay*by%mod, 0,0,ax%mod,0,ay%mod, 0,0,0,bx%mod,by%mod, 0,0,0,0,1,}; ll s1=a0*b0%mod; ll a1=a0*ax%mod+ay;a1=a1%mod; ll b1=b0*bx%mod+by;b1=b1%mod; ll a1b1=a1*b1;a1b1=a1b1%mod; if(n==1) { printf("%I64d\n",s1); continue; } else if(!n) { printf("0\n"); continue; } else { matrix tmp=fast_mod((n-1),p); ll ans=s1*tmp.mat[0][0]%mod+a1b1*tmp.mat[0][1]%mod +tmp.mat[0][2]*a1%mod+tmp.mat[0][3]*b1%mod+tmp.mat[0][4]*1%mod; printf("%I64d\n",ans%mod); } } return 0; }
