number number number

【2017 ACM/ICPC Asia Regional Shenyang Online】number number number

打表找规律+矩阵快速幂

Solution:

规律与斐波那契数列有关。

#include <iostream>
#include <cstdio>
using namespace std;

const int MOD = 998244353;

typedef unsigned long long ULL;

struct Matrix {
    ULL 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] += (v[i][k] * m.v[k][j]) % MOD;
                    ret.v[i][j] %= MOD;
                }
            }
        }
        return ret;
    }
    void operator *= (const Matrix & m) {
        *this = *this * m;
    }
};

Matrix fastPow(Matrix x, ULL n) {
    Matrix ans = {{{1, 0}, {0, 1}}};
    while (n) {
        if (n & 1) ans *= x;
        x *= x;
        n >>= 1;
    }
    return ans;
}

const Matrix trans = {{{1, 1}, {1, 0}}};

int main(void) {
    ios::sync_with_stdio(false);
    ULL k;
    while (cin >> k) {
        if (k == 1) cout << 4 << endl;
        else {
            Matrix transform = fastPow(trans, 2 * (k - 1) - 1);
            cout << (transform.v[0][0] * 8 + transform.v[0][1] * 5 - 1) % MOD << endl;
        }
    }
    return 0;
}