結果
問題 | No.621 3 x N グリッド上のドミノの置き方の数 |
ユーザー |
![]() |
提出日時 | 2017-12-21 01:29:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 3,000 ms |
コード長 | 3,661 bytes |
コンパイル時間 | 2,206 ms |
コンパイル使用メモリ | 179,916 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-16 07:31:27 |
合計ジャッジ時間 | 5,697 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 66 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long signed int LL; typedef long long unsigned int LU; #define incID(i, l, r) for(int i = (l) ; i < (r); i++) #define incII(i, l, r) for(int i = (l) ; i <= (r); i++) #define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--) #define decII(i, l, r) for(int i = (r) ; i >= (l); i--) #define inc(i, n) incID(i, 0, n) #define inc1(i, n) incII(i, 1, n) #define dec(i, n) decID(i, 0, n) #define dec1(i, n) decII(i, 1, n) #define inII(v, l, r) ((l) <= (v) && (v) <= (r)) #define inID(v, l, r) ((l) <= (v) && (v) < (r)) #define PB push_back #define EB emplace_back #define MP make_pair #define FI first #define SE second #define PQ priority_queue #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define FOR(it, v) for(auto it = v.begin(); it != v.end(); ++it) #define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it) template<typename T> bool setmin(T & a, T b) { if(b < a) { a = b; return true; } else { return false; } } template<typename T> bool setmax(T & a, T b) { if(b > a) { a = b; return true; } else { return false; } } template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } } template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } } template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); } template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; } // ---- ---- template<int N> void mat_prod(LL a[N][N], LL b[N][N], LL c[N][N], LL MOD) { // a = b * c; LL d[N][N]; inc(i, N) { inc(j, N) { d[i][j] = 0; } } inc(i, N) { inc(j, N) { inc(k, N) { (d[i][j] += b[i][k] * c[k][j]) %= MOD; } } } inc(i, N) { inc(j, N) { a[i][j] = d[i][j]; } } return; } template<int N> void mat_exp(LL a[N][N], LL b[N][N], LL c, LL MOD) { // a = b ^ c; LL t[60][N][N]; inc(i, N) { inc(j, N) { t[0][i][j] = b[i][j]; } } inc(i, 60 - 1) { mat_prod<N>(t[i + 1], t[i], t[i], MOD); } inc(i, N) { inc(j, N) { a[i][j] = 0; } } inc(i, N) { a[i][i] = 1; } inc(i, 60) { if((c >> i) % 2 == 1) { mat_prod<N>(a, a, t[i], MOD); } } return; } // ---- const int S = 28; LL n, m[S][S], l[S][S], r[S][S], MOD = 1e9 + 7; map<array<int, 3>, int> mp; int main() { cin >> n; int d = 0; inc(x, 64) { int a = x % 4, b = x / 4 % 4, c = x / 16; mp[{ a, b, c }] = -1; if(b == 3 && a == 3) { continue; } if(b == 3 && c == 3) { continue; } if(b == 2 && a != 2 && c != 2) { continue; } if(b == 2 && a == 2 && c == 2) { continue; } if(b != 2 && a == 2) { continue; } if(b != 2 && c == 2) { continue; } mp[{ a, b, c }] = d++; } inc(x, 64) { inc(y, 64) { int xa = x % 4, xb = x / 4 % 4, xc = x / 16; int ya = y % 4, yb = y / 4 % 4, yc = y / 16; if(mp[{ xa, xb, xc }] == -1) { continue; } if(mp[{ ya, yb, yc }] == -1) { continue; } if(xa == 0 && ya != 1) { continue; } if(xb == 0 && yb != 1) { continue; } if(xc == 0 && yc != 1) { continue; } if(xa != 0 && ya == 1) { continue; } if(xb != 0 && yb == 1) { continue; } if(xc != 0 && yc == 1) { continue; } if(xa == 3 && ya == 3) { continue; } if(xb == 3 && yb == 3) { continue; } if(xc == 3 && yc == 3) { continue; } m[mp[{ xa, xb, xc }]][mp[{ ya, yb, yc }]]++; } } l[0][mp[{ 1, 1, 1 }]] = 1; inc(x, 64) { int a = x % 4, b = x / 4 % 4, c = x / 16; if(mp[{ a, b, c }] == -1) { continue; } if(a != 0 && b != 0 && c != 0) { r[mp[{ a, b, c }]][0] = 1; } } mat_exp(m, m, n, MOD); mat_prod(m, l, m, MOD); mat_prod(m, m, r, MOD); cout << m[0][0] << endl; return 0; }