我是巴兰斯 | I'm Balance

· · 个人记录

显然考虑把限制转化到前缀和。限制有两类：

如果直接考虑 DP，需要记录前 k 个 S 值，时间复杂度 O(nk^k)，不可接受。但是不状压又没有什么头绪，所以我们考虑继续状压的思路，但是尝试让 k 的指数减小。

考虑将 S 每 k 个分为一组。枚举每组的总和，也就是枚举所有 S_{ak}，这样枚举的代价就只有 O(k^{\frac{n}{k}}) 了。然后如果我们依次去 DP，最优可以做到 O(k^{\frac{2n}{k}}\text{polylog}(n,k))，已经可以在 k 较大的时候通过 n\leq 66 的部分分了，对于 k 比较小的情况，可以使用 O(n2^k) 的暴力。

考虑一个网格图。枚举了 S_{ak} 之后，一组里面的 S_{ak+r} 对应了一个网格图上，起点为 (0,0)，终点为 (k,S_{ak}-S_{(a-1)k}) 的路径，每一步可以向右或者右上走。这启发我们考虑 LGV 引理，也就是需要将 S_{i+k}-S_{i}\neq \frac{k}{2} 进行一个转化，变成两条路径不交。转化是显然的，令 S'_{ak+r}=S_{ak+r}-\frac{ak}{2}，那么限制就变成了 S'_{i+k}-S'_i\neq 0，也就是路径整体向下平移 \frac{ak}{2}。修改一下坐标系使得所有坐标都非负，就得到：第 a 条折线从 \sum_{i=a+1}^{l}(\frac{k}{2}-L_i) 处开始，在 \sum_{i=a+1}^{l}(\frac{k}{2}-L_i)+L_a 处结束。这里有 L_i 是 S_{ik}-S_{(i-1)k} 表示第 i 组的总和，l 表示组的数量。

注意到 S_{i+k}-S_i 在 i 变化 1 的时候变化不超过 1，所以可知所有 S_{i+k}-S_i-\frac{k}{2} 同号，也就是 \frac{k}{2}-L_i 均同号。两种符号对称，不妨设 L_i<\frac{k}{2}。这时我们已经将问题转化成不相交路径计数的模型了。

我们还需要处理剩下来的一些限制和细节：

  1. 已经确定的前缀对第一组的影响。这对应了限制 S_i<\frac{k}{2}+S_{i-k}，也就是，对第一条折线有一个上界。而第 i+1 条折线在第 i 条折线之下，所以我们直接将这个折线上界视为整个网格的顶端即可。
  2. 最后一组个数不足 k 的情况。那中点就不在 x=k 上，这时候要注意 LGV 引理需要的两个条件是否仍然满足。容易发现我们违背了条件对于左边右边两对有序的起点 (a,b) 和终点 (c,d)，任何两条 a\to d 和 b\to c 的路径必然相交。这是因为我们可以从右下角绕过去。所以我们需要钦定右下角不可以经过。

然后经过一些 DP 的预处理，我们就可以在 O(k^{\frac{n}{k}}(\frac{n}{k})^3+n^3k^2) 的时间里解决整个问题。