浅谈状压状物解法以及复杂度分析

· · 算法·理论

前置知识

位运算 dp 基础数论初中 / 小学数学？

温馨提示：在无特殊说明下，钦定 n,m 同阶。

引入

啥是状压 dp？

先看例题：

P1879

:::info[形式化题意]{open} 在一个有障碍的矩阵中放置物品，要求不能相邻，求方案数。 :::

::::info[解法] 容易想到 dp ，但是无法用二维状态表示，故想到用一个二进制数表示，用一个 n 位的二进制表示，第 i 位表示这一行的第 i 个空是否被填上了，然后暴力枚举然后递推。 时间复杂度 \text{O}(4^nn^2)。

:::info[优化和复杂度分析] 考虑优化：注意到只要有相邻两个二进制位相等便是不合法的，合法状态十分稀疏，因此考虑提前预处理出所有合法的状态。 定义 F_i 为宽为 i 的无障碍行的合法方案数。

显然 F_0=1,F_1=2。

当 i>1 时，考虑第 i 位。

F_i=F_{i-1}+F_{i-2}

时间复杂度优化为 \text{O}(2^n+F_n^2n^2) ，其中 F_i 表示第 i 项斐波那契数列。 ::: ::::

例题

P2704

先想想解法再看。

:::info[解法] 状压前两行，用一个 2m 位的二进制数表示，转移。

不优化时间复杂度：\text{O}(8^nn^2)。

考虑优化，缩减状态：

定义 F_i 为宽为 i 的无障碍行的合法方案数。

显然 F_0=1,F_1=2,F_2=3。

当 i>1 时，考虑第 i 位。

F_i=F_{i-1}+F_{i-3}
x 1 2 3 4 5 6 7 8 9 10
F_x 2 3 4 6 9 13 19 28 41 60

时间复杂度为 \text{O}(F_m^3n) = 2.16\times 10^7(n=10,m=100)。 :::

小练习

P10447

:::info[提示] 状压节点访问情况。 :::

P4363.

:::info[提示] 不告诉你。 :::

插头 dp

::::info[解法]{open}

要求什么

因为覆盖全图的回路必定包含起点，而起点向右走和向下走分别是两种方案，所以答案是覆盖全图的回路的情况乘以二，考虑插头 dp。

插头

什么是插头，顾名思义就是两个互相对插的头？

反正在插头 dp 中，插头就是两个互相对插的头，只要相邻两个格子的插头相对就可以形成一个连接线。

如图便是一个绿色线所对应的红色插头。

按正常人的定义，向上的就是上插头，其他类似，我们要做的就是给每一个格子确定插头，使得它们形成一条哈密顿回路。

轮廓线

分割已决策格子和未决策格子的线。

转移

注意到（CDQ 大人注意力惊人）插头一定不会有这种情况。

轮廓线上从左到右 4 个插头 a,b,c,d 其中 a,c 连通，并且与 b 不连通，b,d 连通。

这样显然无法联通，证明见 CDQ 论文。

所以我们可以用括号序列来匹配。

左括号表示一条联通线的点，用 1 表示；右括号表示一条联通线的终点，用 2 表示；无插头用 0 表示。

位运算跑的飞快所以可以用 4 进制。

设 dp_{i,j,q} 表示在 (i,j) 这个格子，轮廓线状态为 q 的方案数，显然前两维可以压掉，把最后一维哈希一下即可，采用挂表法。

:::success[另一种解法] 打表出所有的状态然后遍历？ :::

具体转移

  1. 当前格子为障碍格子。 判断 mp_{i+1,j} 和 mp_{i,j+1} 是否可以放插头。
  2. 左边和上面都没有插头。 右边和下边不是障碍直接连上。
  3. 左边或上面的插头中只有一个是空插头。 直接延长或可以拐个弯。
  4. 左边为终点，上面为起点。 相当于把两条线连在一起，都赋成 0 即可。
  5. 都为起点 / 终点。 再找到其中一条的另一端，赋成相对的值。
  6. 左边为起点，上面为终点。 最后面转移好了且没有空插头，才能转移。 ::::

为了方便，记 C(x) 为卡特兰数，假定 n, m 同阶，在测试中钦定 n=m.

复杂度分析

轮廓线的状态大概如下：一个长度为 n 的由 ., (, ) 组成的括号序列。

我们考虑先计算长度为 x 的括号序列，方案数为 C(\frac{x}{2})。

那么剩下有 n-x 个 . 使用插板法可得方案数为 C_n^{x}。

乘起来方案数约为：

\sum^n_{x=0} C(\frac{n}{2})C_n^x (2|n)

换一种方式：

\sum^{\lfloor \frac{n}{2}\rfloor}_{x=0}\frac{C_{2x}^xC_{n}^{2x}}{x+1}

时间复杂度上界则为 n^2 乘状态数，所以下次有人问你插头 dp 的复杂度，你可以回答：

\text{O}( n^2\sum^{\lfloor \frac{n}{2}\rfloor}_{x=0}\frac{C_{2x}^xC_{n}^{2x}}{x+1})

验证

:::info[代码]{open} 我代码的核心部分：

FOR(n) {
        FORj(m) {
            int szt = nzt;
            nzt ^= 1;
            ncnt[nzt] = 0;
            memset(hed, 0, sizeof(hed));

            for (int k = 1; k <= ncnt[szt]; k++) {
                K++;
                ztt now = gg(hsb[k].zt[szt]);
                ztt tmp = now;
                int nnt = hsb[k].cnt[szt];
                int ldr = now.dt[0];
                int sdr = now.dt[j];

                if (!mp[i][j]) {
                    if (!ldr && !sdr) {
                        cha(ec(tmp), nnt);
                    }
                    continue;
                }

                if (!ldr && !sdr) {
                    if (mp[i + 1][j] && mp[i][j + 1]) {
                        tmp.dt[0] = 2;
                        tmp.dt[j] = 1;
                        cha(ec(tmp), nnt);
                    }
                }

我们认为 K 是运算次数。 :::

n 运算得到 实际次数
12 2.234\times 10^6 1.333\times 10^6
13 7.070\times 10^6 3.660\times 10^6
14 2.227\times 10^7 1.291\times 10^7
15 6.988\times 10^7 3.566\times 10^7
16 2.185\times 10^8 1.229\times 10^8

数量级相当，故可被认为是正确的。

后记：

测试用矩阵若 2|n 则全是 . 否则除了右下角全是 .，这是为了让状态最多。

个人认为插头 dp 可以增强到 n,m\le 14。

爆 long long 了。

后记

不要简单的认为状压 dp 就是 \text{O}(n^{k_1}k_2^n) 的，其实可以极大地优化。