【HDU-4990】Reading comprehension

【HDU-4990】Reading comprehension

Solution:

看上去是分奇偶的,但是具有统一的递推形式:

记\(a_k\)为第k项的值。

Part 1.当k是偶数时,则\(a_k = a_{k – 1} \times 2 = a_{k – 1} + 2 \times a_{k – 2} + 1\)。

Part 2.当k是奇数时,则\(a_k = a_{k – 1} \times 2 +1 = a_{k – 1} + 2 \times a_{k – 1} + 1\)。

写出变换矩阵就可以解决了。

#include <iostream>

using namespace std;

typedef long long LL;
LL MOD;
struct Matrix {
    LL t[3][3];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
};

const Matrix BASE = {{1, 2, 1, 1, 0, 0, 0, 0, 1}};

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{1, 0, 0, 0, 1, 0, 0, 0, 1}};
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n;
    while (cin >> n >> MOD) {
        if (n == 1) cout << 1 % MOD << "\n";
        else if (n == 2) cout << 2 % MOD << "\n";
        else {
            Matrix trans = powMod(n - 2, BASE);
            LL ans = (trans.t[0][0] * 2 + trans.t[0][1] * 1 + trans.t[0][2]) % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}