#185495 (C++11) No.541 3 x N グリッド上のサイクルの個数

• 問題: No.541 3 x N グリッド上のサイクルの個数
• ユーザー: rickytheta
• 提出日時: 2017-07-01 00:15:42
• 言語: C++11 (gcc 13.3.0)
• 結果: AC
• 実行時間: 11 ms / 2,000 ms
• コード長: 2,399 bytes
• コンパイル時間: 1,593 ms
• コンパイル使用メモリ: 168,148 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-10-04 22:10:28
• 合計ジャッジ時間: 3,465 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
other	AC * 62

ソースコード

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))
// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD
typedef vector<vl> mat;
const int sz = 8*3+2;
mat matmul(mat A, mat B){
  mat R(sz,vl(sz));
  REP(i,sz)REP(j,sz)REP(k,sz)(R[i][j]+=A[i][k]*B[k][j]%MOD)%=MOD;
  return R;
}
int main(){
  ll n;
  cin>>n;
  mat A(sz,vl(sz,0));
  REP(from,3*8)REP(to,3*8){
    int fs = from/3; int fx = from%3;
    int ts = to/3; int tx = to%3;
    if(fx!=tx){
      if(fx==0 && tx==2){
        // must close
        if(ts!=0b101)continue;
        if(fs!=0b100 && fs!=0b001)continue;
      }else if(fx==0 && tx==1){
        // mustn't close
        if(ts!=0b101)continue;
        if(fs!=0b111)continue;
      }else if(fx==2 && tx==0){
        // close
        if(ts!=0b111)continue;
        if(fs!=0b101)continue;
      }else if(fx==1 && tx==0){
        // erase
        if(ts!=0b100 && ts!=0b001)continue;
        if(fs!=0b101)continue;
      }else{
        continue;
      }
    }else{
      if(fx==1){
        if(fs!=0b101)continue;
        if(ts!=0b101)continue;
      }
      if(fx==2){
        if(fs!=0b101)continue;
        if(ts!=0b101)continue;
      }
      if(fx==0){
        if((fs&ts)==0)continue;
        if(ts==0b101)continue;
      }
    }
    A[to][from] = 1;
  }
  int cone = 3*8;
  int cans = 3*8+1;
  A[cans][cans] = 1;
  A[cone][cone] = 1;
  REP(to,3*8){
    int s = to/3; int x = to%3;
    // one
    if(s!=0){
      if(x==0 && s!=0b101){
        A[to][cone] = 1;
      }else if(x==2 && s==0b101){
        A[to][cone] = 1;
      }
    }
    // ans
    if(s!=0){
      if(x!=2){
        A[cans][to] = 1;
      }
    }
  }
  n++;
  mat I(sz,vl(sz,0));
  REP(i,sz)I[i][i] = 1;
  while(n>0){
    if(n&1)I = matmul(A,I);
    A = matmul(A,A);
    n >>= 1;
  }
  cout << I[cans][cone] << endl;
  return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX