参考资料

状态压缩 - 周伟

初级

特殊方格棋盘
在n*n(n≤20)的方格棋盘上放置n 个车,某些格子不能放,求使它们不能互相攻击的方案总数。

#include <cstdio>
#define file(x) "examone." #x
const int N = 25, L = 1 << 20 | 1;
typedef long long ll;
int n, m, a[N];
ll f[L];
int main() {
    freopen(file(in), "r", stdin);
    freopen(file(out), "w", stdout);
    scanf("%d%d", &n ,&m);
    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x] |= 1 << y - 1;
    }
    int l = 1 << n;
    f[0] = 1;
    for (int k = 1; k <= n; k++) {
        for (int s = l - 1; s; s--) {
            for (int x = s&~a[k]; x; x -= x&-x)
                f[s] += f[s&~(x&-x)];
        }
    }
    printf("%lld\n", f[l - 1]);
}

中级

657. 放棋子
给出一个 n x m 的棋盘 (n 、 m≤80,n x m ≤ 80) ,要在棋盘上放 k(k ≤ 20) 个棋子, 使得任意两个棋子不相邻。每次试验随机分配一种方案,求首次放置即出现合法方案的概率,答案用既约分数表示(格式是分母在前)。
预处理每行可能的状态再暴力dp
状态:i行状态s,所有总共放了j个棋子

#include <cstdio>
#include <algorithm>
#define file(x) "examtwo." #x
typedef long long ll;
int c[300], cc[300], num, n, m, k;
ll f[80][300][25];
void dfs(int p, int cnt, int s) {
    if (p > m) {
        c[++num] = s;
        cc[num] = cnt;
        return;
    }
    if (cnt > k) return;
    if (p > 1 && s&(1 << p - 2));
    else dfs(p + 1, cnt + 1, s|(1 << p - 1));
    dfs(p + 1, cnt, s);
}
ll comb(int y, int x) {
    ll r = 1;
    for (int k = 1; k <= x; k++) r *= y - k + 1;
    for (int i = 1; i <= x; i++) r /= i;
    return r;
}
ll gcd(ll x, ll y) {return y ? gcd(y, x%y) : x;}
int main() {
    freopen(file(in), "r", stdin);
    freopen(file(out), "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    if (m > n) std::swap(n, m);
    dfs(1, 0, 0);
    f[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1, s; j <= num; j++) {
            s = c[j];
            for (int h = cc[j]; h <= k; h++) {
                for (int g = 1, ss; g <= num; g++) if (!((ss = c[g])&s)) f[i][s][h] += f[i-1][ss][h - cc[j]];
            }
        }
    }
    ll par = comb(n*m, k), chi = 0;
    for (int i = 0; i < 300; i++) chi += f[n][i][k];
    ll d = gcd(par, chi);
    printf("%lld/%lld\n", par/d, chi/d);
}

高级

1x2骨牌覆盖

$f[i][s]$表示第i行覆盖状态为s,前i-1行完全覆盖的方案数

怎么转移呢?
倒着$f[i-1]$不太好写。
所以找从$f[i][s]$出发能更新到的状态。

dfs(当前列,第i行状态,第i+1行状态) 表示当前列左边的列都被完全覆盖
每次枚举在第i+1行的决策:竖着放,横着放,不放。
列数超出m时用出发时的状态更新i+1行状态。

第一行的答案直接搜出。
利用1~n-1即可更新出2~n的答案。

#include <cstdio>
#include <cstring>
#define file(x) "examfive." #x
const int N = 12, V = 1 << 11 | 1;
typedef long long ll;
int n, m;
ll f[N][V], fr;
inline int set(int x, int p, int v) {
    if (v) return x | (1 << p - 1);
    else return x & ~(1 << p - 1);
}
inline int get(int x, int p) {return x >>(p - 1)&1;}
void dfs(int r, int c, int s0, int s1) {
    if (c > m) {
        f[r + 1][s1] += fr;
        return;
    }
    if (get(s0, c) && get(s0, c + 1)) dfs(r, c + 2, s0, set(set(s1, c, 1), c + 1, 1));
    if (!get(s0, c)) dfs(r, c + 1, set(s0, c, 1), set(s1, c, 1));
    else dfs(r, c + 1, s0, s1);
}
void init(int c, int s) {
    if (c > m) f[1][s] = 1;
    else {
        if (c + 1 <= m) init(c + 2, set(set(s, c, 1), c + 1, 1));
        init(c + 1, s);
    }
}
int main() {
    freopen(file(in), "r", stdin);
    freopen(file(out), "w", stdout);
    while (scanf("%d%d", &n, &m)){
        if (n == 0 && m == 0) break;
        memset(f, 0, sizeof(f));
        init(1, 0);
        for (int i = 1; i < n; i++)
            for (int j = 0; j < 1 << m; j++)
                if (f[i][j]) fr = f[i][j], dfs(i, 1, j, 0);
        printf("%lld\n", f[n][(1 << m) - 1]);
    }
}

1x2 + L型覆盖

L形可以旋转
基本上和上一题都一样。
但是dfs到c列的时候不再表示左边的列完全覆盖,而是表示c-2列及其左边的列完全覆盖。
这样最后更新答案(c=m + 1时)的时候需要判一下m-1是不是完全覆盖,如果是再加上。
因为存在 左右反转的「形 放置,所以最多影响到c-1列,因此我们定义了c-2列及左边完全覆盖。并且容易知道c-2列未覆盖时需要及时剪枝。因为怎么放置都影响不到它了。
代码和以上细节有出入。

#include <cstdio>
#include <cassert>
#define file(x) "examsix." #x
const int N = 1 << 10;
typedef long long ll;
int n, m;
ll f[10][N];
inline int set(int x, int p, int v) {
    if (v) return x | (1 << p - 1);
    else return x & ~(1 << p - 1);
}
inline int get(int x, int p){return x >> (p - 1)&1;}
void init(int c, int s) {
    if (c > m) f[1][s] = 1;
    else {
        if (c + 1 <= m) init(c + 2, set(set(s, c, 1), c + 1, 1));
        init(c + 1, s);
    }
}
ll fr;
void dfs(int r, int c, int s0, int s1) {
    if (c - 2 >= 1 && !get(s0, c - 2)) return;
    if (c > m) {
        if (s0 == (1 << m) - 1) f[r + 1][s1] += fr;
    }
    else {
        if (c + 1 <= m) {
            if (!get(s0, c))  dfs(r, c + 2, set(s0, c, 1), set(set(s1, c, 1), c + 1, 1));
            if (get(s0, c) && !get(s0, c + 1)) dfs(r, c + 2, set(s0, c + 1, 1), set(set(s1, c, 1), c + 1, 1));
            if (get(s0, c)) dfs(r, c + 2, s0, set(set(s1, c, 1), c + 1, 1));
            if (!get(s0, c) && !get(s0, c + 1)) dfs(r, c + 1, set(set(s0, c, 1), c + 1, 1), set(s1, c, 1));
        }
        if (c - 1 >= 1 && !get(s0 ,c) && !get(s0, c - 1)) dfs(r, c + 1, set(set(s0, c, 1), c - 1, 1), set(s1, c, 1));
        if (!get(s0, c)) dfs(r, c + 1, set(s0, c, 1), set(s1, c, 1));
        dfs(r, c + 1, s0, s1);
    }
}
int main() {
    freopen(file(in), "r", stdin);
    freopen(file(out), "w", stdout);
    scanf("%d%d", &n, &m);
    init(1, 0);
    for (int i = 1; i < n; i++)
        for (int s = 0; s < 1 << m; s++) if (fr = f[i][s])
             dfs(i, 1, s, 0);
    printf("%lld\n", f[n][(1 << m) - 1]);
}

1 x r 覆盖

恩……我前几题的做法貌似没法再做了。抄了萌帝的代码。
一次性枚举所有转移。

实战

NOI2000 炮兵阵地

先对每行搜出合法状态再开(i, 第i行状态,第i-1行状态)转移

#include <cstdio>
#include <algorithm>
#define file(x) "cannon." #x
const int N = 61;
int n, m, f[101][N][N], num, s[N], ans, rm[101];
char buf[11];
inline int set(int s, int p, int v) {
    if (v) return s|(1 << p - 1);
    else return s & ~(1 << p - 1);
}
inline int get(int s, int p) {return (s<<p - 1)&1;}
void dfs(int c, int ss) {
    if (c > m) s[++num] = ss;
    else dfs(c + 1, ss), dfs(c + 3, set(ss, c, 1));
}
int main() {
    freopen(file(in), "r", stdin);
    freopen(file(out), "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", buf + 1);
        for (int j = 1; j <= m; j++) rm[i] = set(rm[i], j, buf[j] == 'H');
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        for (int s1 = 1; s1 <= num; s1++) if (!(s[s1]&rm[i]))
            for (int s2 = 1; s2 <= num; s2++) if (!(s[s2]&rm[i - 1]) && !(s[s1]&s[s2]))
                for (int s3 = 1; s3 <= num; s3++) if (!(s[s2]&s[s3]) && !(s[s1]&s[s3])) {
                    if (i > 2 && (s[s3]&rm[i - 2])) continue;
                    int cc = __builtin_popcount(s[s1]);
                    f[i][s1][s2] = std::max(f[i - 1][s2][s3] + cc, f[i][s1][s2]);
                    ans = std::max(ans, f[i][s1][s2]);
                }
    }
    printf("%d\n", ans);
}

2734 HNOI2012 集合选数

//hide 点击查看隐藏的题解
//网上的题解还是挺多的。
//需要注意的就是每一行应该是 x 4x 9x 27x, 这样减少了状态数。x 2x 4x 这样就会tle
//还有就是很多题解说这是矩阵,然而并不是,明明是三角来着……
#include <cstdio>
#include <cstring>
typedef long long ll;
const int M = 1e9 + 1;
int u;
int f[2][int(1<<11)], ans = 1;
bool vis[int(1e5) + 10];
inline void calc(int d) {
    memset(f, 0, sizeof(f));
    int i, j, pj, x;
    f[0][0] = 1;
    for (i = 1, pj = 0; d <= u; i++, d*=2, pj = j) {
        for (j = 1, x = d; x <= u; j++, x*=3) vis[x] = 1;
        j--;
        for (int s = 0; s < 1 << j; s++)
            if ((s&(s>>1)) == 0)
            for (int ss = 0; ss < 1 << pj; ss++)
                if ((s&ss) == 0) f[i&1][s] = (f[i&1][s] + f[(i&1)^1][ss])%M;
        for (int s = 0; s < 1 << pj; s++) f[(i&1)^1][s] = 0;
    }
    i--;
    int c = 0;
    for (int s = 0; s < 1 << pj; s++) c = (c + f[i&1][s])%M;
    ans = 1ll*ans*c%M;
}
int main() {
//    freopen("input", "r", stdin);
    scanf("%d", &u);
    for (int i = 1; i <= u; i++) if (!vis[i]) calc(i);
    printf("%d", ans);
}