poj 3254 狀壓dp

分析：

對于一個序列dp的慣用套路是一個元素一個元素的添加，而對于一個二維數組是一行一行的添加，而且要用一個二進制壓縮來記錄目前行的各種狀态。

這裡 dp[i][s] 表示前 i 行，第i行狀态為 s 時一共有多少種方法。s不是任意的而是有很多生成條件，我先預處理除了所有滿足不相鄰的狀态，然後要滿足限制使用位運算高效滿足的。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define pr(x) cout << #x << ": " << x << "  " 
#define pl(x) cout << #x << ": " << x << endl;

int mod = int();

struct jibancanyang
{
    int n, m;
    bool G[][];
    int  ok[];
    int dp[][ << ];
    int Set[ << ], cnt;

    void pre(int s, int cur = ) {
        if (cur == m) {
            Set[cnt++] = s;
            return;
        }
        pre(s, cur + );
        if (!cur || !((s >> (cur - )) & )) pre(s |  << cur, cur + ); 
    }

    void bug() {
        m = ;
        pre();
        for (int i = ; i < cnt; ++i) pr(Set[i]);
    }


    void fun() {
        while (~scanf("%d%d", &n, &m)) {
            cnt = ;
            pre();
            for (int i = ; i < n; ++i) {
                int s = ;
                for (int j = ; j < m; ++j) {
                    int x; 
                    scanf("%d", &x);
                    if (x) s |=  << j;
                    G[i][j] = x;
                }
                ok[i] = s;
       //         pr(i), pl(s);
            }
            memset(dp, , sizeof(dp));
            for (int i = ; i < n; ++i) {
                int cur = i % , nxt = (i + ) % ;
                for (int t = ; t < cnt; ++t) {
                    int s = Set[t];
                    dp[cur][s] = ;
                    if ((s | ok[i]) == ok[i]) {
                        if (i == ) dp[cur][s] = ;
                        else for (int j = ; j < cnt; ++j) {
                            int sLast = Set[j];
                            if ( (s & sLast) == ) {
                                (dp[cur][s] += dp[nxt][sLast]) %= mod;
                            }
                        }
        //                pr(i), pr(s), pl(dp[cur][s]);
                    }

                }
            }
            int ans = ;
            for (int i = ; i < cnt; ++i) {
                ans += dp[(n - ) % ][Set[i]];
                ans %= mod;
            }
            printf("%d\n", ans);
        }
    }
}ac;

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    ac.fun();
    return ;
}