hdu 4686 （等比解法）

这题也可以用矩阵快速幂来轻松解决，但是在比赛的时候没有构造出矩阵，然后直接用数学的方法把这题ac了，方法如下：

可以得出an和bn都是类等比数列，类等比数列暂且定义为等比数列之间的加减乘除组合后的数列，an,bn如下：

an=A0*Ax^n+Ay*(Ax^(n-1)+Ax^(n-2)+……+Ax^1+Ax^0).(n>=1)

bn=B0*Bx^n+By*(Bx^(n-1)+Bx^(n-2)+……+Bx^1+Bx^0).(n>=1)

令Fn=an*bn,所以Fn也是类等比数列；

然后sum{Fn}就是一些等比数列求和的问题了，等比数列求和可以用公式的快速幂+逆元实现；

不过在这里还要注意一下Ax和Bx等于1和0的情况，因为当Ax和Bx等于1时就变成了等差数列，当为0时就变成了常数列，

任何数列和常数列相乘性质不变，等差和等比数列相乘我们可以用错位相减的方法求解，这个方法记得在高中做数学题时经常用到；

具体的推导公式就不一一列出了，反正有好一大坨；

代码如下（15~31ms）：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<bitset>
#include<string>
#include<queue>
#include<deque>
#include<ctype.h>
#include<vector>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<functional>
#include<algorithm>

using namespace std;

#define mod 1000000007

long long mult(long long x,long long y){
    long long sum=0;
    while(y){
        if(y&1) sum=(sum+x)%mod;
        x=(x+x)%mod;
        y>>=1;
    }
    return sum;
}
long long power(long long x,long long y){
    long long sum=1;x%=mod;
    while(y){
        if(y&1) sum=(x*sum)%mod;
        x=x*x%mod;
        y>>=1;
    }
    return sum;
}

long long caldiff(long long a0,long long a1,long long n){
    return mult((a0+a0+mult(a1,n-1))%mod,n)*power(2,mod-2)%mod;
}

long long calratio(long long a0,long long a1,long long n){
    long long ans=a0%mod;
    ans=ans*((power(a1,n)+mod-1)%mod)%mod;
    ans=ans*power(a1-1,mod-2)%mod;
    return ans;
}

long long cal2(long long a,long long n){
    long long ans=(2*mod-n%mod-1+mult(a,n))%mod;
    ans=((ans*power(a,n+1))%mod+a)%mod;
    ans=ans*power(a-1,mod-2)%mod*power(a-1,mod-2)%mod;
    return ans;
}
int main(){
    long long n,A[3],B[3],ans,i,t;
    while(scanf("%I64d",&n)!=EOF){
        scanf("%I64d%I64d%I64d",&A[0],&A[1],&A[2]);
        scanf("%I64d%I64d%I64d",&B[0],&B[1],&B[2]);
        if(n==0){
            printf("0\n");continue;
        }
        if(n==1){
            ans=A[0]*B[0]%mod;
            printf("%d\n",int(ans));
            continue;
        }
        if(A[1]==0&&B[1]==0){
            ans=A[2]*B[2]%mod;
            ans=mult(ans,n-1);
            ans=(ans+(A[0]*B[0])%mod)%mod;
        }
        else if(A[1]+B[1]==1){
            if(B[1]==1)for(i=0;i<3;i++) swap(A[i],B[i]);
            ans=A[0]*B[0]%mod;
            ans=(ans+mult((A[0]*B[2])%mod,n-1))%mod;
            ans=(ans+caldiff(0,A[2]*B[2]%mod,n))%mod;
        }
        else if(A[1]==1&&B[1]==1){
            ans=mult(A[0]*B[0]%mod,n);
            ans=(ans+caldiff(0,(B[0]*A[2]%mod+A[0]*B[2]%mod)%mod,n))%mod;
            ans=(ans+mult(A[2]*B[2]%mod,mult(mult(n-1,n),2*n-1))*power(6,mod-2))%mod;
        }
        else if(B[1]==0&&A[1]>1||A[1]==0&&B[1]>1){
            if(A[1]==0) for(i=0;i<3;i++) swap(A[i],B[i]);
            ans=(A[0]*B[0])%mod;
            t=((A[0]*B[2])%mod+B[2]*A[2]%mod*power(A[1]-1,mod-2)%mod)%mod;
            ans=(ans+t*calratio(A[1],A[1],n-1)%mod)%mod;
            ans=(ans+mod-mult((A[2]*B[2]%mod*power(A[1]-1,mod-2))%mod,n-1))%mod;
        }
        else if(B[1]==1&&A[1]>1||A[1]==1&&B[1]>1){
            if(A[1]==1)  for(i=0;i<3;i++) swap(A[i],B[i]);
            ans=(A[0]*B[0])%mod;
            t=ans+A[2]*B[0]%mod*power(A[1]-1,mod-2)%mod;
            ans=(ans+t*calratio(A[1],A[1],n-1)%mod)%mod;
            t=(A[0]*B[2]%mod+B[2]*A[2]%mod*power(A[1]-1,mod-2)%mod)%mod;
            ans=(ans+t*cal2(A[1],n-1))%mod;
            ans=(ans+mod-caldiff(0,A[2]*B[2]%mod*power(A[1]-1,mod-2),n))%mod;
            ans=(ans+mod-mult(A[2]*B[0]%mod*power(A[1]-1,mod-2)%mod,n-1))%mod;
        }
        else {
            ans=(A[0]*B[0])%mod;
            t=A[0]*B[0]%mod;
            t=(t+A[0]*B[2]%mod*power(B[1]-1,mod-2)%mod)%mod;
            t=(t+B[0]*A[2]%mod*power(A[1]-1,mod-2)%mod)%mod;
            t=(t+A[2]*B[2]%mod*power(A[1]-1,mod-2)%mod*power(B[1]-1,mod-2)%mod)%mod;
            ans=(ans+t*calratio(A[1]*B[1]%mod,A[1]*B[1]%mod,n-1)%mod)%mod;
            t=(mod-A[0]*B[2]%mod*power(B[1]-1,mod-2)%mod)%mod;
            t=(t+mod-A[2]*B[2]%mod*power(A[1]-1,mod-2)%mod*power(B[1]-1,mod-2)%mod)%mod;
            ans=(ans+t*calratio(A[1],A[1],n-1)%mod)%mod;
            t=(mod-B[0]*A[2]%mod*power(A[1]-1,mod-2)%mod)%mod;
            t=(t+mod-A[2]*B[2]%mod*power(A[1]-1,mod-2)%mod*power(B[1]-1,mod-2)%mod)%mod;
            ans=(ans+t*calratio(B[1],B[1],n-1)%mod)%mod;
            t=A[2]*B[2]%mod*power(A[1]-1,mod-2)%mod*power(B[1]-1,mod-2)%mod;
            ans=(ans+mult(t,n-1))%mod;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}