题目链接

Description

An Arc of Dream is a curve defined by following function:
where
a0 = A0
ai = ai-1AX+AY
b0 = B0
bi = bi-1BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

Input

There are multiple test cases. Process to the End of File.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 1018, and all the other integers are no more than 2×109.

Output

For each test case, output AoD(N) modulo 1,000,000,007.

Sample Input

1
1 2 3
4 5 6
2
1 2 3
4 5 6
3
1 2 3
4 5 6

Sample Output

4
134
1902

题意：

如公式

题解：

这道题目可以构造矩阵，首先我们知道AoD(n) 可以由AoD(n-1)+a[n-1]*b[n-1]求得。这样我们将这些因素构成矩阵即可使用矩阵快速幂优化。注意n==0的时候输出0.

代码：

#include 
      
       using namespace std;const long long mod = 1000000007;long long ans[5];long long s[5][5];long long tans[5];long long ts[5][5];long long ret[5][5];long long cal[5][5];long long n,A0,B0,AX,AY,BX,BY;void mul(long long a[][5],long long b[][5],long long c[][5]){    for (int i = 0; i < 5; i++){        for (int j = 0; j < 5; j++){            c[i][j] = 0;            for (int k = 0; k < 5; k++){                c[i][j] = (c[i][j] + a[i][k]*b[k][j]%mod)%mod;            }             }    }}void init(){    ans[0] = A0; ans[1] = B0; ans[2] = A0*B0%mod; ans[3] = ans[2]; ans[4] = 1;    s[0][0] = AX;s[0][1] = s[0][2] = s[0][3] = 0; s[0][4] = AY;    s[1][0] = 0;s[1][1] = BX;s[1][2] = s[1][3] = 0;s[1][4] = BY;    s[2][0] = AX*BY%mod; s[2][1] = AY*BX%mod; s[2][2] = AX*BX%mod; s[2][3] = 0;s[2][4] = AY*BY%mod;    s[3][0] = AX*BY%mod; s[3][1] = AY*BX%mod; s[3][2] = AX*BX%mod; s[3][3] = 1;s[3][4] = AY*BY%mod;    s[4][0] = s[4][1] = s[4][2] = s[4][3] = 0;s[4][4] = 1;}void cop(long long a[][5],long long b[][5]){    for (int i = 0;i < 5; i++){        for (int j = 0; j < 5; j++)            a[i][j] = b[i][j];        }    }void solve(){    if (n == 0){        printf("0\n");        return ;        }    n--;         cop(cal,s);memset(ret,0,sizeof ret);for (int i = 0; i < 5; i++) ret[i][i] = 1;    while (n){        if (n%2){            mul(ret,cal,ts);            cop(ret,ts);            }        mul(cal,cal,ts);        cop(cal,ts);        n /= 2;    }    long long rt = 0;    for (int i = 0; i < 5; i++){        rt = (rt + ans[i]*ret[3][i]%mod)%mod;        }    printf("%lld\n",rt);}int main(){    while (~scanf("%lld %lld %lld %lld %lld %lld %lld",&n,&A0,&AX,&AY,&B0,&BX,&BY)){        init();        solve();    }    return 0;}