5
21
2016
0

【脑洞】谈谈一类骨牌覆盖问题

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll MOD = 19999997;

struct matrix {
    ll a, b, c, d;
    matrix() : a(0), b(1), c(1), d(1) {}
    matrix operator * (const matrix &m) const {
        matrix tmp;
        tmp.a = (a * m.a + b * m.c) % MOD;
        tmp.b = (a * m.b + b * m.d) % MOD;
        tmp.c = (c * m.a + d * m.c) % MOD;
        tmp.d = (c * m.b + d * m.d) % MOD;
        return tmp;
    }
};

matrix pow(const matrix &a, int n) {
    matrix tmp;
    if (n == 0 || n == 1) return tmp;
    tmp = pow(a, n / 2);
    if (n & 1) {
        tmp = tmp * tmp * a;
    } else {
        tmp = tmp * tmp;
    }
    return tmp;
}

int main() {
    ll n;
    matrix a, b;
    while (cin >> n) {
        b = pow(a, n);
        cout << b.d << endl;
    }
    return 0;
}
#include <iostream>
using namespace std;

typedef unsigned long long ll;
const ll MOD = 12357;

ll N;
ll a[5];

void solve() {
    a[0] = 0;
    a[1] = 2;
    a[2] = 3;
    for (int i = 3; i <= N; ++i) {
        if (i & 1) {
            a[i%5] = (2*a[(i-1+5)%5] + a[(i-2+5)%5]) % MOD;
        } else {
            a[i%5] = (3*a[(i-2+5)%5] + a[(i-3+5)%5]) % MOD;
        }
    }
    cout << a[N%5] << endl;
}

int main() {
    while (cin >> N) {
        if (N & 1) {
            cout << "0" << endl;
        } else {
            solve();
        }
    }
    return 0;
}

当然也可以用矩阵快速幂进行加速.

Category: 树套树 | Tags: Fibonacci 矩阵 滚动数组 | Read Count: 204

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com