模意义下的世界
5
21
2016
21
2016
【脑洞】谈谈一类骨牌覆盖问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #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;} |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #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;} |
当然也可以用矩阵快速幂进行加速.
