結果
問題 |
No.621 3 x N グリッド上のドミノの置き方の数
|
ユーザー |
|
提出日時 | 2017-12-21 21:55:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 3,000 ms |
コード長 | 2,772 bytes |
コンパイル時間 | 1,894 ms |
コンパイル使用メモリ | 177,312 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-17 22:41:14 |
合計ジャッジ時間 | 9,458 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 66 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define mt make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; const int MOD = (int)1e9 + 7; /* 行列の積(mod) 行列Aと行列Bの積を返す O(n^3) */ vector<vector<int> > mulMatMod(const vector<vector<int> > &A, const vector<vector<int> > &B) { auto n = A.size(), m = A[0].size(), p = B[0].size(); vector<vector<int> > res(n, vector<int>(p)); for (int i = 0; i < n; ++i)for (int j = 0; j < p; ++j) for (int k = 0; k < m; ++k) res[i][j] = (int)((res[i][j] + (long long)A[i][k] * B[k][j]) % MOD); return res; } /* 行列Aの累乗(mod)を返す O(n^3 * log(k)) */ vector<vector<int> > powMatMod(vector<vector<int> > A, long long k) { auto n = A.size(); vector<vector<int> > res(n, vector<int>(n)); for (int i = 0; i < n; ++i)res[i][i] = 1; while (k) { if (k % 2)res = mulMatMod(res, A); k /= 2; A = mulMatMod(A, A); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); const int R = 1 << 6; const int START = 0b111; const int GOAL[] = { 0b111,0b011,0b101,0b010,0b110 }; ll N; int a[3][3]; cin >> N; vi D[3] = { {},{0,0,1,0},{0,0,0,1} }; vector<vi> A(R, vi(R)); rep(S, R) { rep(i, 3)rep(j, 3)rep(k, 2) { MEM(a, 0); rep(l, 6) { int x = l / 3, y = l % 3; a[x][y] = S >> l & 1; } int ok = 1, d[] = { i,j,k }; rep(l, 3) { for (int m = 0; m < sz(D[d[l]]); m += 2) { int x = 1 + D[d[l]][m]; int y = l + D[d[l]][m + 1]; if (a[x][y])ok = 0; else a[x][y] = 1; } } rep(y, 3) { if (!a[0][y] && !a[1][y])ok = 0; if (y < 2 && !a[0][y] && !a[0][y + 1])ok = 0; } int T = 0; rep(l, 6) { int x = l / 3 + 1, y = l % 3; if (a[x][y])T |= 1 << l; } if(ok)A[T][S]++; } } A = powMatMod(A, N); vector<vi> v(R, vi(1)); v[START][0] = 1; v = mulMatMod(A, v); ll ans = 0; rep(i, 5)ans += v[GOAL[i]][0]; cout << ans%MOD << endl; }