HDU - Arc of Dream(矩阵快速幂)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4686
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)

Problem Description

An Arc of Dream is a curve defined by following function:

where
a0 = A0
ai = ai-1*AX+AY
b0 = B0
bi = bi-1*BX+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

Problem solving report:

Description: 让你求Aod(n)的值，其中每个元素的计算公式已给出。
Problem solving: 因为n比较大，即使是O(n)也是一样会超时，所以我们采用矩阵快速幂的方式来解题。

a[i]=a[i-1]*AX+AY;
b[i]=b[i-1]*BX+BY;
a[i]*b[i]=a[i-1]*b[i-1]*AX*BX+a[i-1]*AX*BY+b[i-1]*BX*AY+AY*BY;
S[i]=S[i-1]+a[i]*b[i]=S[i-1]+a[i-1]*b[i-1]*AX*BX+a[i-1]*AX*BY+b[i-1]*BX*AY+AY*BY;
根据上式可知

根据S[i]，一定需要S[i-1]，a[i-1]*b[i-1]，a[i-1]，b[i-1]，常数。矩阵大小为5.

构造初始矩阵ANS0

转换矩阵a.使得

根据上面4个公式得:

现在要求 AoD(n)=ans(n-1), 求出ans*a^(n-1)的第一行第一个元素就行了。

另外注意要判断一下n等于0的情况，这个判断条件很重要，没有就会TLE。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
struct mat {
    ll m[6][6];
    mat() {
       memset(m, 0, sizeof(m));
    }
}a, ans;
mat mul(mat a, mat b) {
    mat p;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            for (int k = 0; k < 5; k++)
                p.m[i][j] = (p.m[i][j] + (a.m[i][k] * b.m[k][j]) % MOD) % MOD;
    return p;
}
mat power(mat a, ll k) {
    mat p;
    for (int i = 0; i < 5; i++)
        p.m[i][i] = 1;
    while (k) {
        if (k & 1)
            p = mul(p, a);
        a = mul(a, a);
        k >>= 1;
    }
    return p;
}
int main() {
    ll n, a_, b_, ax, ay, bx, by;
    while (~scanf("%lld", &n)) {
        scanf("%lld%lld%lld", &a_, &ax, &ay);
        scanf("%lld%lld%lld", &b_, &bx, &by);
        if (!n) {
            printf("0\n");
            continue;
        }
        a.m[0][0] = 1;
        a.m[1][0] = ax * bx % MOD, a.m[1][1] = ax * bx % MOD;
        a.m[2][0] = ax * by % MOD, a.m[2][1] = ax * by % MOD, a.m[2][2] = ax % MOD;
        a.m[3][0] = ay * bx % MOD, a.m[3][1] = ay * bx % MOD, a.m[3][2] = 0, a.m[3][3] = bx % MOD;
        a.m[4][0] = ay * by % MOD, a.m[4][1] = ay * by % MOD, a.m[4][2] = ay % MOD, a.m[4][3] = by % MOD, a.m[4][4] = 1;
        ans.m[0][0] = a_ * b_ % MOD, ans.m[0][1] = a_ * b_ % MOD, ans.m[0][2] = a_ % MOD, ans.m[0][3] = b_ % MOD, ans.m[0][4] = 1;
        ans = mul(ans, power(a, n - 1));
        printf("%lld\n", ans.m[0][0]);
    }
    return 0;
}