HDU 4686 – Arc of Dream [矩阵快速幂]

点击打开HDU题目链接

题意

给你两个数列的首项和递推公式,让你求前N个的分别乘积之和,N最大有10^18.

分析

以前做过一个2333的矩阵的题,记得题解上说过矩阵特别适合用来表达多个数的变幻,而这个题也是如此,而且N很大,就想到了用矩阵快速幂。根据Ai和Bi及Ai×Bi的递推公式,瞎凑了一会儿就推出了5*5的矩阵。如下所示:

A矩阵:

选区_007

B矩阵:

选区_008

C++代码

 

#include <cstdio>
#include <map>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

typedef unsigned long long ULL;

const int MAXN = 7;
const ULL MOD = 1000000007;
int N = 5;

struct Mat {
    ULL a[MAXN][MAXN];
    Mat() { memset(a, 0, sizeof(a)); }
    Mat multiMod(const Mat & y, const ULL mod) {
        Mat res;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < N; k++)
                    res.a[i][j] = (res.a[i][j] + (a[i][k] * y.a[k][j]) % mod) % mod;
        return res;
    }
    Mat powerMod(ULL k, ULL mod) {
        Mat res, base = *this;
        for(int i = 0; i < MAXN; i++)
            res.a[i][i] = 1;
        while(k > 0) {
            if(k & 1)
                res = res.multiMod(base, mod);
            base = base.multiMod(base, mod);
            k >>= 1;
        }
        return res;
    }
};


int main() {
    ULL n, a0, ax, ay, b0, bx, by;
    while(~scanf("%I64u", &n)) {
        scanf("%I64u%I64u%I64u", &a0, &ax, &ay);
        scanf("%I64u%I64u%I64u", &b0, &bx, &by);
        if(n == 0) {
            printf("0\n");
            continue;
        }
        if(n == 1) {
            printf("%I64u\n", (a0*b0) % MOD);
            continue;
        }
        Mat A, B;
        A.a[0][0] = (a0*b0) % MOD;
        A.a[1][0] = a0 % MOD;
        A.a[2][0] = b0 % MOD;
        A.a[3][0] = 1;
        A.a[4][0] = 0;

        B.a[0][0] = (ax*bx)%MOD;
        B.a[0][1] = (ax*by)%MOD;
        B.a[0][2] = (ay*bx)%MOD;
        B.a[0][3] = (ay*by)%MOD;
        B.a[1][1] = ax % MOD;
        B.a[1][3] = ay % MOD;
        B.a[2][2] = bx % MOD;
        B.a[2][3] = by % MOD;
        B.a[3][3] = 1LL;
        B.a[4][0] = B.a[4][4] = 1LL;

        B = B.powerMod(n-1, MOD);
        B = B.multiMod(A, MOD);
        printf("%I64u\n", (B.a[0][0] + B.a[4][0]) % MOD);
    }
    return 0;
}

欢迎留言