【PGBATTLE2020_せんべい4】ドミノ

過去問：https://products.sint.co.jp/q_list_2020
解答：https://products.sint.co.jp/hubfs/resource/topsic/pgb2020/code.pdf

解説を理解したあと実装した結果、解説コードと全く同じになりました。

・H=2のときフィボナッチ数列があらわれますが、ここからの発展性は見つかりませんでした。
・1をでっぱり、0を平坦とみなし、1<<5通りのhash同士について、凹凸が組み合わせられるか見ていきます。

Q. 凹凸の組み合わせ？
A. 

1 は横置き開始地点。01 か 10 が遷移成立。
0 は
1. 1->0なら横置きの終端。
2. 0->0なら縦置き。0どうしが隣接していれば遷移成立。

Q. 3 6の場合。
1. DP[0][000]=1 からの状態遷移は3通り。
※(000)は本来ありえない。ただの初期条件
000 -> 001 
x      xa
x      xa
x      xbb
      
000 -> 100
x      xaa
x      xb
x      xb
      
000 -> 111
x      xaa
x      xbb
x      xcc

DP[1][001] = 1
DP[1][100] = 1
DP[1][111] = 1

2. もう一段思考整理
001 -> 000 
xa     xac
xa     xac
xbb    xbb

001 -> 110
xa     xacc
xa     xadd
xbb    xbb


100 -> 000 
xaa    xaa
xb     xbc
xb     xbc

100 -> 011
xaa    xaa
xb     xbcc
xb     xbdd


111 -> 000
xaa    xaa
xbb    xbb
xcc    xcc

DP[2][000] = 3
DP[2][110] = 1
DP[2][011] = 1
になる。

A. 
(3, 6)
41
000:1 0 3 0 11 0 41 
001:0 1 0 4 0 15 0 
010:0 0 0 0 0 0 0 
011:0 0 1 0 4 0 15 
100:0 1 0 4 0 15 0 
101:0 0 0 0 0 0 0 
110:0 0 1 0 4 0 15 
111:0 1 0 3 0 11 0 

Q. 00の縦置きが成立する条件？
A.

0が縦置きだとすると

10000
00100
00001
11100
11001
10011
00111

といった、0が2個隣接したような置き方。

101 は縦置きできないとみなす。
010 も。

組み合わせ方がわかれば、
DP[index][hash]=組み合わせ数で管理。
初期条件はDP[0][00000]=1
解答はDP[W][00000]

実装

bool matrix[1<<5][1<<5]; // pre, nx
map<ll, bool> goodhash; // goodhash[hash]=true なら縦置き状態遷移できる
ll DP[10010][1<<5];
ll H, W;

void debug(){
 rep(j, (1<<H)){
   string bits;
   rep(k, 5){
     if((j>>k)&1) bits+="1";
     else bits+="0";
   }
   reverse(all(bits));
   cout << bits << ":";
   rep(i, W+1){
     cout << DP[i][j] << " ";
   }
   cout << endl;
 }
}

int main(){
 cincout();
 
 cin >> H >> W;
 if(H%2 && W%2){
   cout << 0 << endl;
   return 0;
 }
 // goodhash
 rep(i, (1<<H)){
   vector<ll> pos;
   ll cnts = __builtin_popcountll(i);
   if(cnts%2) continue;
   rep(h, H){
     if ((i>>h)&1) pos.push_back(h);
   }
   bool ok=true;
   rep(c, cnts/2){
     if(pos[c*2] != pos[c*2+1]-1) ok=false;
   }
   if(ok) goodhash[i] = true;
 }
 
 // matrix 凹凸が成立する組み合わせかどうか
 rep(pre, (1<<H)){
   rep(nx, (1<<H)){
     //11はありえない
     //00の縦置きができるか判定
     ll check=0;
     rep(h, H){
       if ( ispop(pre, h) && ispop(nx, h) ) check=oo;
       if ( !ispop(pre, h) && !ispop(nx, h) ) check |= 1<<h;
     }
     if (goodhash.count(check)) matrix[pre][nx] = true;
   }
 }
 
 DP[0][0]=1;
 rep(i, W){
   rep(pre, (1<<H)){
     rep(nx, (1<<H)){
       if(matrix[pre][nx]) ( DP[i+1][nx] += DP[i][pre] ) %= MOD;
     }
   }
 }
 cout << DP[W][0] << endl;
//  debug();
}