結果
問題 | No.579 3 x N グリッド上のサイクルのサイズ(hard) |
ユーザー |
👑 ![]() |
提出日時 | 2020-10-23 18:19:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,955 bytes |
コンパイル時間 | 1,726 ms |
コンパイル使用メモリ | 169,960 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-21 10:20:35 |
合計ジャッジ時間 | 4,104 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 80 |
ソースコード
#include<bits/stdc++.h>using namespace std;using LL = long long;using ULL = unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)// ---- // LJ-- // L_J- // L__J //// -LJ- // -L_J // --LJ // LJLJ //// LLJJ // <==> //const ULL M = 1000000007;const int matrix_sz = 20;struct Matrix{ULL X[matrix_sz][matrix_sz] = {};static Matrix id(){ Matrix res; rep(i, matrix_sz) res[i][i] = 1; return res; }ULL* operator[](int x){ return X[x]; }const ULL* operator[](int x) const { return X[x]; }Matrix pow(ULL N) const;};Matrix operator*(Matrix l, Matrix r){Matrix res;rep(i, matrix_sz) rep(j, matrix_sz) rep(k, matrix_sz)res[i][j] = (res[i][j] + l[i][k] * r[k][j]) % M;return res;}Matrix Matrix::pow(ULL N) const{if (N == 0) return id();Matrix res = pow(N / 2);res = res * res;if (N % 2 == 1) res = res * *this;return res;}const ULL Gconst1[matrix_sz / 2][matrix_sz / 2] ={{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0 },{ 0, 1, 1, 1, 0, 0, 0, 1, 0, 1 },{ 0, 1, 1, 1, 1, 1, 0, 0, 0, 1 },{ 0, 1, 1, 1, 1, 1, 1, 0, 1, 1 },{ 0, 0, 1, 1, 1, 1, 0, 0, 0, 1 },{ 0, 0, 1, 1, 1, 1, 1, 0, 0, 1 },{ 0, 0, 0, 1, 0, 1, 1, 1, 0, 1 },{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 0 },{ 0, 1, 0, 0, 0, 0, 1, 0, 1, 1 },{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }};const ULL Gconst2[matrix_sz / 2][matrix_sz / 2] ={{ 0, 2, 3, 4, 2, 3, 2, 4, 0, 0 },{ 0, 2, 3, 4, 0, 0, 0, 4, 0, 2 },{ 0, 3, 2, 3, 3, 4, 0, 0, 0, 3 },{ 0, 4, 3, 2, 4, 3, 4, 0, 4, 4 },{ 0, 0, 3, 4, 2, 3, 0, 0, 0, 2 },{ 0, 0, 4, 3, 3, 2, 3, 0, 0, 3 },{ 0, 0, 0, 4, 0, 3, 2, 4, 0, 2 },{ 0, 0, 0, 4, 0, 0, 0, 4, 0, 0 },{ 0, 4, 0, 0, 0, 0, 4, 0, 4, 4 },{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }};int main(){Matrix G;rep(i, 10) rep(j, 10){G[i * 2][j * 2] = Gconst1[i][j];G[i * 2][j * 2 + 1] = Gconst2[i][j];G[i * 2 + 1][j * 2] = 0;G[i * 2 + 1][j * 2 + 1] = Gconst1[i][j];}ULL N; scanf("%llu", &N);G = G.pow(N + 1);cout << G[0][19] << endl;return 0;}