[AGC017F] Zigzag 题解

StayAlone · 2023-08-04 13:48:44 · 题解

比较显然的解法就不说了，直接讲正解。

状压，用轮廓线 dp 的套路，设 f_{i, j, s} 表示满足下列要求的方案数：

• 安排了前 i-1 条线，第 i 条线走到了第 j 行；
• 将一个长度为 n-1 的 0/1 串用二进制压成 s，用这个 s 可以表示一条从第一行走到第 n 行的折线，其中 s_1\sim s_{j-1} 表示从第一行走到现在的第 j 行的走法，再用 s_j\sim s_{n-1} 表示的折线作为一条 「分界线」，接下来的路径不能在这条分界线的左边。

初值比较显然。枚举每一种 s，如果这个 s 符合输入的 K 条限制，则有 f_{1, n, s} = 1。

这里 dp 我使用「推」的方式，即已知 f_{i, j, s}，找到这个状态会给哪些别的状态贡献。

考虑寻找 f_{i, j, s} 会给哪些别的状态贡献。

分如下情况：

当 j=n 时，即现在已经是最底端，f_{i+1,1,s}\gets f_{i, j,s}。

其它情况下，考虑向左走还是向右走。

图中黑线是分界线。

如图，例如 j=2，分界线的下一步向右，那么不可以向左走。

因此，当且仅当分界线的下一步向左，且给定的限制中未规定向右（即规定向左走或者无规定）时，可以向左走，走到下一步之后分界线不变。此时 f_{i,j+1,s}\gets f_{i, j, s}。

向右走的情况相对复杂。

如图，若分界线的下一步向右，且未规定向左，则可以向右走，且分界线不变：f_{i,j+1,s}\gets f_{i, j, s}。

如图，例如 j=2，分界线的下一步向左。若要向右走，分界线发生了改变，从黑线变成了红线。

具体怎样改变的呢？我们将红线黑线的二进制写下来，注意是倒着写的。

1 1 0 0 0 黑线
1 0 0 1 0 红线
5 4 3 2 1 编号

我们发现，s_{j} 变成了 1，且 s_{j+1}\sim s_{n-1} 中下标最小的 1 变成了 0。这个 1 可以用如下代码获得：

int p = lowbit(s >> j) << j;

也就是先将后 j 位移除，再获得最低位，最后要还原。

这种情况下，数组的推导不得不用代码表示了：

int p = lowbit(s >> j) << j;
(f[i][j + 1][(s | (1 << j - 1)) - p] += f[i][j][s]) %= mod;

但是容易想到一种特殊情况，那就是 s_{j+1}\sim s_{n-1} 全都是 0，如图：

这种情况下只需要把 s_{j} 变成 1 即可。实际写代码时可以无需处理这种特殊情况，因为找到的 lowbit 为 0。