题目链接：uva
11270 - Tiling Dominoes

题目大意：用1∗2木块将给出的n∗m大小的矩阵填满的方法总数。

解题思路：插头dp的裸题，dp[i][s]表示第i块位置。而且该位置相应的行数的状态为s的时候的总情况数。0表示为竖放预留留的位置，1表示填上的位置。无论是竖放还是横放。而且第一位状态用滚动数组优化空间。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

int n, m;

ll dp[2][(1<<11)+5];

int main () {

    while (scanf("%d%d", &n, &m) == 2) {

        int now = 0, pre = 1;

        if (n < m)

            swap(n, m);

        int e = (1<<m)-1;

        memset(dp[now], 0, sizeof(dp[now]));

        dp[now][e] = 1;

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) {

                swap(now, pre);

                memset(dp[now], 0, sizeof(dp[now]));

                for (int s = 0; s <= e; s++) {

                    if (j && !(s&(1<<(j-1))) && (s&(1<<j)))

                        dp[now][s | (1<<(j-1))] += dp[pre][s];

                    dp[now][s ^ (1<<j)] += dp[pre][s];

                }

            }

        }

        printf("%lld\n", dp[now][e]);

    }

    return 0;

}