# Hardwood Floor

## 题目描述

The banquet hall of Computer Scientists’ Palace has a rectangular form of the size $M \times N$. It is necessary to lay hardwood floors in the hall. There are wood pieces of two forms:

• rectangles ($2 \times 1$)
• corners (squares $2 \times 2$ without one $1 \times 1$ square)

You have to determine $X$ – the number of ways to cover the banquet hall.
Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 11;
int n, m, f[N][1 << N];
void input() { io > n > m; }
void update(int x, int y, int s, int val, int p) {
if (y == (1 << m) - 1) { f[x][s] += val; return; }
for (int i = p; i < m; ++ i)
if (! (y & 1 << i)) {
if (! (s & 1 << i)) {
update(x, y | 1 << i, s | 1 << i, val, i + 1);
if (i && ! (s & 1 << i - 1)) update(x, y | 1 << i, s | 1 << i | 1 << i - 1, val, i + 1);
if (i < m - 1 && ! (s & 1 << i + 1)) update(x, y | 1 << i, s | 1 << i | 1 << i + 1, val, i + 1);
}
if (i < m - 1 && ! (y & 1 << i + 1)) {
update(x, y | 1 << i | 1 << i + 1, s, val, i + 2);
if (! (s & 1 << i)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i, val, i + 2);
if (! (s & 1 << i + 1)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i + 1, val, i + 2);
}
}
}
void process() {
f[0][(1 << m) - 1] = 1;
for (int i = 0; i <= n; ++ i)
for (int j = 0; j < 1 << m; ++ j)
if (f[i][j]) update(i + 1, j, 0, f[i][j], 0);
io < f[n + 1][0] < '\n';
}

public:
void solve() { input(), process(); }
} solver;

signed main() {
solver.solve();
return 0;
}


418 I'm a teapot