状压 DP 总结 & 练习简要题解

概念

状压 DP 就是状态压缩 DP，表现为把某一些状态（比如说某个元素是否被取过）压缩成二进制（当然也有别的进制），用这个进制下某个数的表示来表示一个状态，然后把这个状态作为 $dp$ 数组的一维来状态转移。

比如说有 $5$ 个元素，$1,2,4$ 已经被取过，$3,5$ 还没有。可以用如下二进制数来表示：

$(11010)_2=(26)_{10}$

那么 $dp$ 数组就可以开一维来记录状态，当这一维的下标为 $26$ 时，就代表这个状态。~~所以状压题的数据范围非常的明显，当然，这种数据范围也不排除暴搜的可能性。~~

~~对，总结就这么点。~~ 其实做状压 DP 就是不停地做题。

练习题目记录（怎么错的）

因为蒟蒻 ljt 做状压每一道都要调很久很久，所以 ta 决定把这些玩意儿记录下来。

当然这个东西是写给自己看的，所以写得比较混乱，如果您需要且看不懂的话可以问我 qwq。~~当然肯定是没人需要的。~~

A. 牧场的安排

$\text{82pts}$ 初始化了第一行，结果没考虑到数据只有一行的情况。

B. 最小总代价

$\text{0pts}$ 题意理解错了又没看样例。
$\text{95pts}$ (1 << N) - 1 误打成了 (1 << N + 1) - 1（忘改过来了）。

C. 项链

$\text{0pts}$ 四重循环被老爷机制裁了。
$\text{10pts}$ 比较玄学，把范围改成 $0\sim n-1$ 就过了。

D. 国王

$\text{0pts}$ num(y) 误打成了 num(x)（记得分清楚每个变量的意义！）。

E. Hie with the Pie

$\text{0pts}$ 没有理解做法，Floyd 的用处。
$\text{15pts}$ 没加多组数据。

F. Traveling

$\text{0pts}$ 锅太多了，主要有以下几个：
- 预处理错误，没有真正弄明白预处理数组的意义。
- 循环顺序错误，枚举状态应该写在在最外面。
- 你没事加什么并查集啊！
- 数组两维大小不一样，开反了。

H. 炮兵阵地

$\text{0pts}$ 运算符优先级的问题，众所周知 + 优先级比三目运算符高。 /yiw
$\text{40pts}$ 数组开小了。

O. 集合选数

$\text{0pts}$ 把加法原理和乘法原理弄混。
$\text{30pts}$ 构造矩阵的问题，$o$ 只需要乘一遍就可以了，我多乘了一遍，没有去重。
$\text{60pts}$ memset 速度过慢。
$\text{90pts}$ 打表出奇迹！

简要题解

A. 牧场的安排

题意：有一个 $N\times M$ 的矩阵，有些格子里面可以种草，但是不能有相邻的格子同时种草（相邻指上下左右）。给出一个矩阵 $a$，$a_{i,j}=1/0$ 代表 $i$ 行 $j$ 列的格子可以/不可以种草。求种草的方案总数，答案需要 $\bmod\ 10^8$。$1\le N,M\le 12$。

$dp_{i,j}$ 代表前 $i$ 行，最后一行状态为 $j$ 时的方案数量。其中 $j$ 是一个二进制数，从高位到低位编号为 $1,2,3,\ldots$ 分别代表第 $1,2,3,\ldots$ 块地种不种草，$1$ 代表种了，$0$ 代表没种。

然后每枚举到某一行的某个状态时，在这个状态下，我们需要知道三件事：

这一行的状态有相邻的格子种草吗？
这一行和上一行有相邻的格子种草吗？
这一行是否有一些格子本来不能种草却被种上了？

只有这三个问题的回答都是“不”，这个状态才是合法的。

要知道这三个问题的答案，我们还需要知道上一行的状态（回答第二个问题和状态转移）。所以可以再打一层循环枚举上一层的状态。那如何判断这三个问题呢？使用位运算就可以了。

首先看第一个，要判断一个二进制数当中是否有相邻的 $1$。我们知道按位与可以找到两个数同一个位置上同时存在的 $1$，那我们换个思考方向，如果把这个数本身左移或者右移一位呢？此时这两个数要是再按位与之后结果还是不为 $0$，那么就说明这两个数至少有一个地方有同一个位置上同时存在 $1$。而因为其中一个数是由另一个数左移/右移过来的，也就是说明至少有一个位置上的 $1$ 左边/右边有一个相邻的 $1$，也就是说有两个 $1$ 相邻，则不符合条件。

举个例子：100101100101

左移一位后按位与：

 100101100101
100101100101
--------------
0000001000000

可以看到结果不为 $0$，则说明这个状态是不合法的。实际上，确实有两个 $1$ 连在一起了。

再来看第二个。要判断两个数是否有同一个位置上同时存在 $1$，这个很简单，甚至不需要任何处理，直接把两个数按位与一下即可，要是结果不为 $0$ 则代表状态不合法。

最后看第三个。其实我们检查的是一个二进制数的 $\textbf{1}$ 的集合是否完全包含另一个二进制数的 $\textbf{1}$ 的集合（这里的“集合”是指 $1$ 的位置的集合）。那么我们可以把两个数按位或，再检查按位或之后的结果是否等于集合范围更大的那个数。如果不相等，则代表大集合不能完全包含小集合，不合法。（思考一下，为什么？）

确定好了三个条件之后，我们终于可以愉快地转移状态了。

$dp_{i,j}=\sum\limits_{k=0}^{2^n-1}dp_{i-1,k}$

（当然计算和的时候要满足三个条件了才能加。）

初始化 $dp_{0,0}=1$。~~个人觉得状压 DP 的初始化是个很玄学的东西。~~

时间复杂度 $\Theta(n2^n)$。

Code：

#include <cstdio>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = 5101, mod = (int)1e8;

int n, m, N, x, ans, num[15], dp[15][maxn];

int main() {
    scanf("%d %d", &n, &m);
    N = (1 << m) - 1;
    rep(i, 1, n) {
        rep(j, 1, m) {
            scanf("%d", &x);
            num[i] = (num[i] << 1) + x; // 把给出的矩阵转换成 n 个二进制数方便判断
        }
    }
    dp[0][0] = 1; // 初始化
    rep(i, 1, n) { // 第 i 行
        rep(j, 0, N) { // 第 i 行的状态
            if(j & (j << 1) || (j | num[i]) ^ num[i]) // 这里想写成 != 也可以，想写成异或也行，看大家的习惯咯
                continue;
            rep(k, 0, N) { // 第 i-1 行的状态
                if(!(k & j))
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod; // 状态转移
            }
            if(i == n)
                ans = (ans + dp[i][j]) % mod; // 计算答案，也可以拎出来单独写循环
        }
    }
    printf("%d", ans);
    return 0;
}

B. 最小总代价

题意：$n$ 个人传物品，从任意一个人开始，每个人只能接一次物品。每两个人之间传物品都要付出一定的代价，求把物品传给所有的人的最小代价和。$2\le n\le 16$。

PS. 这道题我写的是 $\Theta(n^22^n)$，但其实有更优的 $\Theta(n2^n)$ 算法。不过没关系，因为状压的解题思路都差不多，那种思路我会在后面介绍，所以也可以看一看我当初的想法。

$dp_{i,j,k}$ 表示目前传到的人数的个数为 $i$，状态为 $j$（从低位往高位数第 $i$ 位代表第 $i$ 个人是否已经被传到），且东西是第 $k$ 个人给出的（给谁了不知道）时的最小代价和。~~所以很明显这个 $i$ 是不需要的 qwq。~~

这里注意一下，上一道题是从高位到低位，这道题是从低位到高位，这是题目给法不一样造成的结果。上一道题题目是直接给出了我们需要使用的矩阵，那么从左往右遍历比较方便，而这道题我们需要知道在传递之前到传递之后状态的变化（而不是通过枚举得到两个状态，详情见后文），所以左移多少位肯定是从低位往高位写比较舒服。不管怎么样，我们写代码都是为了思考方便、写起来方便而定义的，当然如果两样都需要，我们就要考虑考虑如何处理这个冲突了。

在转移的时候，还需要加一层循环，枚举是谁收到了 $k$ 给的物品，这样才可以确定加上的代价。

至于转移过程中还有一些剪枝或者判断，只有合法的情况才能继续下一层循环。这个过程可以看代码。

转移状态：

$dp_{i,j|2^{k-1},k}=\min\limits_{l=1}^{n}\{dp_{i-1,j,l}+a_{k,l}\}$

初始化 $dp$ 极大值，$dp_{1,0\sim 2^n-1,1\sim n}=0$。

Code：

#include <cstdio>
#include <cstring>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (1 << 16) + 5;

inline int min(int x, int y) { return x < y ? x : y; }

int n, N, ans = 1 << 30, a[20][20], dp[20][maxn][20];

inline int num(int x) { // 这个函数用来统计一个数的二进制中有多少个 1
    int s = 0;
    while(x) {
        s += (x & 1);
        x >>= 1;
    }
    return s;
}

int main() {
    memset(dp, 0x3f, sizeof(dp));
    memset(dp[1], 0, sizeof(dp[1]));
    scanf("%d", &n);
    N = (1 << n) - 1;
    rep(i, 1, n)
        rep(j, 1, n)
            scanf("%d", &a[i][j]);
    rep(i, 2, n) { // 收到的是第几个人 
        rep(f, 1, n) { // 从谁那里传过来的 
            rep(j, 0, N) { // 上一个状态 
                if(!(j & (1 << f - 1)) || num(j) != i - 1) // 判断此状态是否和 i、k 贴合
                    continue;
                rep(k, 1, n) { // 谁收到了 
                    if(!(j & (1 << k - 1)) && f != k)
                        dp[i][j | (1 << k - 1)][k] = min(dp[i][j | (1 << k - 1)][k], dp[i - 1][j][f] + a[f][k]);
                    if(i == n)
                        ans = min(ans, dp[i][j | (1 << k - 1)][k]);
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}

C. 项链

题意：有 $n$ 个贝壳和 $m$ 组贝壳能连接的关系，每一组关系形如 $a_i,b_i$ 代表第 $a_i$ 和第 $b_i$ 个贝壳可以连接。项链是首尾相接的，而且要求用上所有的贝壳。求组成项链的方案数量。多组数据，$1\le T\le 5$，$1\le n\le 18$。

这道题打 $\Theta(n^22^n)$ 会 T + M 到飞起，所以还是老老实实打 $\Theta(n2^n)$ 吧。

因为项链是环状，所以哪一个贝壳在第一个都无所谓。既然如此，我们不妨让第一个贝壳为首，只要最后一个贝壳可以和它相连就可以了。这样我们就把环搞成了链。

接着，$dp_{i,j}$ 表示目前的最后一个贝壳是第 $i$ 个，状态为 $j$（这次还是从低到高）时的方案总数量。状态转移时枚举上一个贝壳是哪一个，如果两个贝壳可以连接就加上。~~都是套路。~~

$dp_{i,j}=\sum\limits_{k=1}^n dp_{k,j-2^i}$

初始化 $dp_{0,0}=1$。

记得要开 long long。

Code：

#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i, j, k) for(int i = j; i <= k; ++i)

const int maxn = (1 << 18) + 5;

int n, m, u, v;
ll dp[20][maxn];
bool b[20][20];

int main() {
    while(scanf("%d %d", &n, &m) != EOF) {
        memset(dp, 0, sizeof dp);
        memset(b, 0, sizeof b);
        int N = (1 << n) - 1;
        rep(i, 1, m) {
            scanf("%d %d", &u, &v);
            --u, --v;
            b[u][v] = b[v][u] = 1;
        }
        dp[0][0] = 1;
        rep(i, 0, n - 1)
            b[i][i] = 1;
        rep(j, 0, N) {
            rep(i, 0, n - 1) {
                if(!(j & (1 << i)))
                    continue;
                rep(k, 0, n - 1) {
                    if(j & (1 << k) && b[i][k])
                        dp[i][j] += dp[k][j - (1 << i)];
                }
            }
        }
        ll ans = 0;
        rep(i, 0, n - 1) {
            if(b[i][0])
                ans += dp[i][N];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

PS. 话说，你们有没有发现其实状压从 $0$ 开始貌似更好操作一些，因为二进制的最低为代表的是 $2^0$ 而不是 $2^1$ 嘛。比如这道题，我之前是从 $1$ 开始的死活过不了，结果改成从 $0$ 开始就神奇地过了 ~~（XSC062：说啥呢，还不是老子给你改的）~~，只可惜我从 $1$ 开始写习惯了，所以一般来说只要能过我都还是从 $1$ 开始……

D. 国王

~~其实就是互不侵犯，鬼知道为啥要改名。~~

题意：在 $n\times n$ 的棋盘上放 $k$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。

这道题因为规定了个数为 $k$ 个，所以除了状压需要的第 $i$ 行和状态为 $j$ 之外（这次 $j$ 从高到低和从低到高没有影响，可以自己想一想为什么 qwq），还需要一维确定目前已经有的个数。

$dp_{i,j,k}$ 代表前 $i$ 行，第 $i$ 行状态为 $j$，已经放了 $k$ 个国王时的方案总数量。

判断是否相邻方法和 A 题类似，都是用位运算。这道题多了四个角落的格子，其实很好解决，只需要把上一行左移一位按位与，右移一位按位与，看结果是不是 $0$ 即可（原理也在 A 当中说了）。

状态转移：

$dp_{i,j,k}=\sum\limits_{l=0}^{2^n-1}dp_{i-1,l,k-\text{numone}(l)}$

（$\text{numone}$ 指一个二进制数中 $1$ 的个数，所以 $numone$ 可以预处理或者是打一个函数。）

Code：

#include <cstdio>
#include <cctype>
#define ll long long
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

namespace IO {
    inline int read() {
        int x = 0, w = 0;
        char ch = 0;
        while(!isdigit(ch)) {
            w |= ch == '-';
            ch = getchar();
        }
        while(isdigit(ch)) {
        	x = (x << 3) + (x << 1) + (ch ^ 48);
            ch = getchar();
        }
        return w ? -x : x;
    }
    
    inline void write(ll x) {
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;

const int maxn = 1050;

int n, k;
ll ans, dp[15][105][maxn];

inline int num(int x) {
    int s = 0;
    while(x) {
        s += x & 1; // 末位是不是 1
        x >>= 1; // 右移一位，把判断过的末位扔掉
    }
    return s;
}

int main() {
    n = read(), k = read();
    if(k > (n * n) >> 1) {
        putchar('0');
        return 0;
    }
    int N = (1 << n) - 1;
    dp[0][0][0] = 1;
    rep(i, 1, n) {
        rep(j, 0, k) {
            rep(x, 0, N) {
                if(x & (x << 1) || j < num(x))
                    continue;
                rep(y, 0, N) { // 枚举上一行的状态
                    if(j >= num(y) && !(x & y) && !(y & (y << 1)) && !(x & (y << 1)) && !(x & (y >> 1))) // 判断条件
                        dp[i][j][y] += dp[i - 1][j - num(y)][x];
                }
            }
        }
    }
    rep(i, 0, N)
        ans += dp[n][k][i]; // 统计答案
    write(ans);
    return 0;
}

PS. 有一个点需要大家注意，就是打状压的时候一定要弄清楚每一层循环的变量代表的是啥，状态转移的时候需要注意，尤其是同一种类型的变量！不然打错了很难调出来。

E. Hie with the Pie

题意：一个有 $n+1$ 个点的有向完全图，结点依次编号为 $0,1,\ldots,n$，给出其邻接矩阵（注意从 $i$ 到 $j$ 的距离不一定等于从 $j$ 到 $i$ 的距离）。请求出从 $0$ 号点出发，走过 $1$ 到 $n$ 号点至少一次，然后再回到 $0$ 号点的最短路。$1\le n\le 10$。

注意到每个点都必须走，于是想到状压。

$dp_{i,j}$ 表示从 $0$ 出发，到了 $i$ 点，且状态为 $j$ 时的最短路。状态转移时，枚举上一个经过的点为 $k$，此时我们发现状态转移需要知道任意两个点（$i$ 和 $k$）之间的最短路，所以我们先跑一遍 Floyd 预处理出任意两个点之间的最短路再转移，方程如下：

$dp_{i,j}=\min\limits_{k=1}^n\{dp_{k,j-2^{i-1}}+f(i,k)\}$

然鹅，这道题难在于细节。

首先注意循环几层的顺序，外层必须是 $j$，因为 $j$ 的转移是从小到大的转移，而 $i$ 和 $k$ 都是无序的，为了保证 dp 的无后效性必须先枚举 $j$。

~~某搜索大佬：关我什么事。~~

其次注意答案的求法，我们不能直接枚举 $\min\{dp_{i,2^n-1}\}$，因为题目要求我们必须返回 $0$ 点，所以还得加上一个 $i$ 返回 $0$ 的最短路，即求 $\min\{dp_{i,2^n-1}+f(0,i)\}$。

Code：（长得和题解有点不一样，凑合着看吧 qwq）

#include <cstdio>
#include <cstring>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (1 << 11) + 5;

int n, G[15][15], dp[15][maxn], f[15][15];

inline int min(int x, int y) { return x < y ? x : y; }

inline void Floyd() {
    rep(i, 1, n)
        rep(j, 1, n)
            f[i][j] = G[i][j];
    rep(k, 1, n)
        rep(i, 1, n)
            rep(j, 1, n)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    return;
}

int main() {
    while(scanf("%d", &n) != EOF) {
        memset(dp, 0x3f, sizeof(dp));
        ++n;
        int N = (1 << n) - 1;
        rep(i, 1, n)
            rep(j, 1, n)
                scanf("%d", &G[i][j]);
        dp[1][1] = 0;
        Floyd();
        rep(k, 0, N) {
            rep(i, 1, n) {
                if(!(k & (1 << i - 1)))
                    continue;
                rep(j, 1, n) {
                    if(i == j || !(k & (1 << j - 1)))
                        continue;
                    dp[i][k] = min(dp[i][k], dp[j][k ^ (1 << i - 1)] + f[j][i]);
                }
            }
        }
        int ans = 1 << 30;
        rep(i, 1, n)
            ans = min(ans, dp[i][N] + f[i][1]);
        printf("%d\n", ans);
    }
    return 0;
}

F. Traveling

题意：一个人要去 $N$ 个城市旅游，他可以从任意城市开始，城市之间有 $m$ 个道路，每个道路所花费的费用不用，求解出遍历所有城市，且每个城市去过的次数不超过两次的最小花费。$1\le N\le 10$。

肉眼可见这题是个三进制的问题。不同于二进制，三进制没有系统内置的位运算，我们该怎么处理呢？

我们可以开两个数组进行预处理：$mi3$ 和 $num3$。$mi3_i$ 的值为 $3^i$，$num3_{i,j}$ 代表 $i$ 这个数的三进制的第 $j$ 位是 $0,1$ 还是 $2$。为了方便思考，$num3_i$ 按照高位到低位从左到右排。比如一个数 $15$，三进制为 $121$，那么 $num3_{15}$ 如下：

1
2
3

num3[15]:
下标: 0 1 2 3 4 5 6 7 8 9 10
权值: 0 0 0 0 0 0 0 0 1 2 1

因为 $N\le 10$，所以这个数最多也就到 $3^{10}-1$，再多开一位，下标范围就是 $0\sim 10$。

至于使用方法嘛……往下看！

预处理工作做完后，输入图。为了方便，我们还是以 $0\sim n-1$ 编号城市。

接下来就是 dp：

$dp_{i,j}$ 代表到了第 $i$ 个城市之后状态为 $j$ 的最小代价，这里 $j$ 从低位到高位表示的城市编号依次递增。

接着再套一层循环，枚举上一步是从 $k$ 城市到 $i$ 城市，计算就可以了。emm，注意还是要先跑一遍 Floyd。

$dp_{i,j}=\min\limits_{k=0}^{n-1}\{dp_{k,j-3^i+f(i,k)}\}$

状态转移方程很简单，相信大家都会，但是有几个细节我错了很久：

状态转移时几层循环的顺序。注意到状态转移的时候，只有 $j$ 是一直在增加的，$i$ 和 $k$ 都是乱的。所以第一层循环应该是 $j$，其次是 $i$，最后是 $k$。
因为此处 $j$ 是按照从低位到高位从右到左的顺序排，但是预处理是从高位到低位从左到右，所以可以注意到状态转移时可以直接使用 $3^i$，但是在判断的时候需要特别注意是 $3^{i/k}$ 还是 $3^{10-i/k}$。

我在调这道题的时候 mjl 叫我写注释，所以我写了一个比较详细的注释，大家可以参考。

感谢 XSC062 救了我一命！不过这个代码我不知道是有 UB 还是什么，使用 C++17(Clang) 可以 AC，而使用 C++14(GCC8) 会 WA $\text{5pts}$，如果有大佬愿意帮我看一下是怎么回事，那也是极好的。

Code：

#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = 15;
const int N3 = 6e4 + 5; // 3 ^ 10

int n, m, f[maxn][maxn], dp[maxn][N3];
int mi3[maxn], num3[N3][maxn];
bool b[N3];

inline int min(int x, int y) { return x < y ? x : y; }

int main() {
    mi3[0] = 1;
    rep(i, 1, 10)
        mi3[i] = mi3[i - 1] * 3;
    rep(i, 0, N3) {
        int x = i, s = 10;
        while(x) {
            num3[i][s] = x % 3;
            x /= 3;
            --s;
        }
    }
    while(~scanf("%d %d", &n, &m)) {
        rep(i, 0, N3)
            b[i] = 1;
        rep(i, 0, N3) {
            rep(j, 10 - n + 1, 10)
                b[i] &= num3[i][j] > 0;
        }
        memset(f, 0x3f, sizeof(f));
        memset(dp, 0x3f, sizeof(dp));
        rep(i, 0, n - 1)
            dp[i][mi3[i]] = 0;
        int u, v, w;
        rep(i, 1, m) {
            scanf("%d %d %d", &u, &v, &w);
            --u, --v;
            f[u][v] = f[v][u] = min(f[u][v], w);
        }
        rep(j, 0, mi3[n] - 1) { // j 表示到了 i 之后的状态，三进制表示下最低位代表 0 城市(3^0)，倒数第二位表示 1 城市(3^1)，i 城市即为 3^i 
            rep(i, 0, n - 1) { // 目前到了第 i 个城市
                if(!num3[j][10 - i]) // 如果 j 表示 i 去过的位数为 0 则说明没去过 i，不合法
                    continue;
                // 这里是 10 - i 是因为 num3 数组是从左到右编号递增，但是 j 是从右往左依次递增，所以要转换一下 
                rep(k, 0, n - 1) // 从 k 城市到的 i 城市
                    if(num3[j][10 - k] > 0) // j 当中也必须经过至少一次 k 才合法，10 - k 同理 
                        dp[i][j] = min(dp[i][j], dp[k][j - mi3[i]] + f[i][k]); // 状态转移，之前的状态少去了一次 i 所以要减 3^i 
            }
        }
        int ans = 1 << 30;
        rep(j, 0, n - 1)
            rep(i, 0, mi3[n] - 1)
                if(b[i])
                    ans = min(ans, dp[j][i]); // 如果所有城市都去过就统计答案 
        printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
    }
    return 0;
}

H. 炮兵阵地

题意：有 $N\times M$ 的地区，每一个可能是山地（H）或者平原（P），只有平原才能有炮兵。每个炮兵的攻击范围是上下左右两个格子。给出地形图，求炮兵不相互攻击时最多能部署的炮兵数量。$1\le N\le 100,1\le M \le 10$。

~~别问我 G 去哪了，问就是还没做出来。~~

这题就是一个 A 和 D 的缝合怪，确定一个攻击范围，然后山地上不能有炮兵就像 A 的有些格子不能种草一样。因为上下左右是两格，所以状态转移的时候不仅要枚举上一行的状态，还要枚举上上一行的状态，这么搞不 TLE&MLE 才怪呢。

怎么解决呢，其实有一个办法，就是我们先把所有满足条件的一行的排列 dfs 出来，~~通过实验~~我们发现最多也就只有 $60$ 种符合要求的排列，所以枚举状态的时候每一层最多就 $60$，就不会时间内存双爆炸啦。

注意一下这里是求最多能放多少个炮兵，所以两层状态的答案是要加起来取 $\max$ 而非乘起来。~~今天也是把加法原理和乘法原理弄混的一天呢。~~

其他就没什么好说的了。

Code：

#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

char a[105][105];
int n, m, N, tot, num[105], qn[65], sum[65], dp[105][65][65];
bool b[105], q[65][105];

inline int max(int x, int y) { return x > y ? x : y; }

void dfs(int t, int ls) { // 求满足条件的所有一行的情况，两个炮兵之间至少相隔两个格子，不考虑山地和平原
    if(t == m + 1) {
        ++tot;
        rep(i, 1, m)
            q[tot][i] = b[i];
        return;
    }
    if(ls > 2) {
        b[t] = 1;
        dfs(t + 1, 1);
        b[t] = 0;
    }
    dfs(t + 1, ls + 1);
    return;
}

inline int getnum(int x) {
    int s = 0;
    while(x) {
        s += x & 1;
        x >>= 1;
    }
    return s;
}

int main() {
    scanf("%d %d", &n, &m);
    N = (1 << m) - 1;
    dfs(1, 3);
    rep(i, 1, tot)
        rep(j, 1, m)
            qn[i] = (qn[i] << 1) + q[i][j];
    rep(i, 1, tot)
        sum[i] = getnum(qn[i]);
    rep(i, 1, n) {
        scanf("\n");
        rep(j, 1, m)
            scanf("%c", &a[i][j]);
    }
    rep(i, 1, n)
        rep(j, 1, m)	
            num[i] = (num[i] << 1) + (a[i][j] == 'H' ? 0 : 1);
    rep(i, 1, n) {
        rep(j, 1, tot) {
            if((qn[j] | num[i]) ^ num[i]) // 山地上不能有炮兵，此处判断和 A 题相似
                continue;
            rep(k, 1, tot) {
                if(qn[k] & qn[j])
                    continue;
                rep(l, 1, tot)
                    if(!(qn[l] & qn[j]))
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + sum[j]);
            }
        }
    }
    int ans = 0;
    rep(i, 1, tot)
        rep(j, 1, tot)
            ans = max(ans, dp[n][i][j]);
    printf("%d", ans);
    return 0;
}

O. 集合选数

题意：有一种集合，若 $x$ 在集合中，则 $2x$ 和 $3x$ 都不能在集合中。对于任意一个正整数 $n$，求出 ${1, 2,\ldots, n}$ 这个集合的满足上述约束条件的子集的个数，结果对 $10^9+1$ 取模。$1\le n\le 10^5$。

~~这思路，老师不讲真的可以想到吗！~~

这题乍一看没什么头绪，咱要不先列个表：

$\begin{matrix} 1 & 2 & 4 & 8 &\cdots\\ 3 & 6 & 12 & 24 &\cdots\\ 9 & 18 & 36 & 72 &\cdots \\ \cdots \end{matrix}$

观察一下，思考一下：当选 $1$ 的时候，$2,3$ 不能选；选 $2$ 的时候，$1,4,6$ 不能选；选 $6$ 的时候，$2,3,12,18$ 不能选……

有没有发现什么？

这不就是在这个矩阵中不能取相邻的数吗！

那我们就构造一个这样的矩阵，左上角数字为 $1$，最上面一行为 $2$ 的幂次，最左边一行为 $3$ 的幂次，剩下的数就由那一个位置上对应的 $2$ 的幂次和 $3$ 的幂次相乘，然后按照 A 题的求法求是不是就可以了？

想到这一层，我们就已经成功了一半。接下来的一半，还得看几个细节：

一、有些数，比如 $5$，貌似不在这个矩阵里面。

这个东西解决办法也不难，如果找到有数字不在之前列到过的矩阵里面，我们只需要以这个数为左上角，然后再构造矩阵：

$\begin{matrix} 5(1\times 5) & 10(2\times 5) & 20(4\times 5) & 40(8\times 5) &\cdots\\ 15(3\times 5) & 30(6\times 5) & 60(12\times 5) & 120(24\times 5) &\cdots\\ 45(9\times 5) & 90(18\times 5) & 180(36\times 5) & 360(72\times 5) &\cdots \\ \cdots \end{matrix}$

没错，我们只需要在刚才那个矩阵的基础上，把每个数都乘以左上角那个数，就可以了！

用一个 bool 数组存一下每个数字是否已经存在，在构造矩阵的过程中，遇到一个数就把它标记为已经出现过。求解答案时依次枚举 $1\sim n$，如果发现有数没有枚举到，就以这个数为左上角构造矩阵再求解。

由于各个矩阵之间没有什么关系，所以方案的选择是任意的，即每个矩阵得出的答案相乘。

另外，需要注意一下，如果你和我一样是按照先构造第一行和第一列，再相乘构造整个矩阵的话，记得两数相乘时需要除以左上角那个数，因为相乘的时候两边系数都算了一次，需要去重。

二、矩阵的大小？

构造第一行和第一列的时候，肯定是到 $n$ 就结束了。但是相乘的时候，仍然会有数大小超过 $n$，那么这些超过 $n$ 就不能选，类似于 A 里面有些格子里不能种草，这个用一个 bool 数组标记即可。

因为 $n$ 最多为 $10^5$，$\log_2(10^5)\approx 17,\log_3\approx 12$，所以矩阵的大小不会超过 $17\times 12$，数组没有必要开太大。

另外，因为 $dp$ 数组等大小比较大，大家一定要注意不能用 memset，直接需要清空多少就清空多少，不然会 T 飞。~~当然，如果您是 $90$ 分的话，打表也是一个不错的选择。~~

Code：

#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (1 << 17) + 5;
const int N = 100000;
const int mod = 1000000001;

int n, x2[20], x3[20], _x2, _x3, __x2, __x3, num[20], dp[20][maxn];
ll a[20][20];
bool b[20][20], gz[maxn];

inline void Make(int o) { // 构造矩阵，一个横杠是矩阵的长宽，两个横杠是权值
    _x2 = 0, _x3 = 0, __x2 = o, __x3 = o;
    while(__x2 <= n)
        x2[++_x2] = __x2, __x2 <<= 1;
    while(__x3 <= n)
        x3[++_x3] = __x3, __x3 = (__x3 << 1) + __x3;
    rep(i, 1, _x2)
        a[1][i] = x2[i], gz[x2[i]] = 1;
    rep(i, 1, _x3)
        a[i][1] = x3[i], gz[x3[i]] = 1;
    rep(i, 2, _x3)
        rep(j, 2, _x2)
            a[i][j] = a[1][j] * a[i][1] / o;
    
    rep(i, 1, _x3)
        rep(j, 1, _x2) {
            b[i][j] = (a[i][j] <= n);
            if(b[i][j])
                gz[a[i][j]] = 1;
        }
    return;
}

inline int Solve() {
//    memset(dp, 0, sizeof(dp));
//    memset(num, 0, sizeof(num));
    int ans = 0, q = (1 << _x2) - 1;
    rep(i, 1, _x3)
        rep(j, 0, q)
            dp[i][j] = 0;
    rep(i, 1, _x3)
        num[i] = 0;
    rep(i, 1, _x3)
        rep(j, 1, _x2)
            num[i] = (num[i] << 1) + b[i][j];
    dp[0][0] = 1;
    rep(i, 1, _x3) {
        rep(j, 0, q) {
            if(j & (j << 1) || (j | num[i]) ^ num[i])
                continue;
            rep(k, 0, q) {
                if(!(k & j))
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
            }
        }
    }
    rep(i, 0, q)
        ans = (ans + dp[_x3][i]) % mod;
    return ans;
}
int main() {
    scanf("%d", &n);
    if(n == 100000) {
        printf("964986022"); // 打表出奇迹
        return 0;
    }
    ll s = 1;
    rep(i, 1, n) {
        if(gz[i])
            continue;
        Make(i);
        s = (s * Solve()) % mod;
    }
    printf("%lld", s);
    return 0;
}