【HDU-4565】So Easy!【矩阵快速幂+向上取整的处理】

【HDU-4565】So Easy!【矩阵快速幂+向上取整的处理】

问题链接:https://vjudge.net/problem/HDU-4565

Solution:

关键在于找到不变形式\(A+B\sqrt{b}\),写出前几个n对应的A和B,列个表格就可以很快找到转移规律。

解决向上取整问题办法是本题的亮点,下面链接中的博文。

参考了:https://blog.csdn.net/Ramay7/article/details/50947293

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long LL;
LL MOD, a, b;
struct Matrix {
    LL v[2][2];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
        return ret;
    }
};

Matrix fastPow(int p, Matrix base) {
    Matrix ret = {a, 0, 1, 0};
    while (p) {
        if (p & 1) ret = base * ret;
        base = base * base;
        p >>= 1;
    }
    return ret;
}

int main(void) {
    int n;
    while (~scanf("%lld%lld%d%lld", &a, &b, &n, &MOD)) {
        Matrix base = {a, b, 1, a};
        base = fastPow(n - 1, base);
        printf("%lld\n", base.v[0][0] * 2 % MOD);
    }
    return 0;
}