ZOJ 2563 Long Dominoes by iloahz@Attiix

zoj2563.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 31;
const int MAXS = 512;

int n, m;
long long f[2][MAXS][MAXS];

long long dp(int m, int n){
    int s = 1 << m;
    int l = 0, r = 1;
    memset(f, 0, sizeof(f));
    f[l][0][0] = 1;
    for (int i = 0;i < n;i++){
        for (int j = 0;j < s;j++){
            for (int k = 0;k < s;k++){
                f[r][j][k] = 0;
            }
        }
        for (int j = 0;j < s;j++){
            for (int k = 0;k < s;k++){
                if (f[l][j][k]){
                    for (int b = 0;b < s;b++){
                        if ((b & j) == 0 && (b & k) == 0){
                            int x = j | b;
                            for (int p = 7;p < s;p <<= 1)
                                if ((x & p) == 0) x |= p;
                            if (x + 1 == s) f[r][k | b][b] += f[l][j][k];
                        }
                    }
                }
            }
        }
        l ^= 1;
        r ^= 1;
    }
    return f[l][0][0];
}

int main(){
#ifdef  ATTIIX
    freopen("zju2563.in", "r", stdin);
#endif
    while (~scanf("%d%d", &m, &n) && (n > 0)){
        printf("%lld\n", dp(m, n));
    }
    return 0;
}