自动搬运

查看原文

来自洛谷，原作者为

	ForgotMe 花与剑无痕，高挂一轮明灯。银蝶染旧梦，生死莫再问。

搬运于2025-08-24 23:05:51，当前版本为作者最后更新于2024-11-08 20:42:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

答辩 dp 题。

设 $s_{x,y}$ 表示 $(x,y)$ 处的符号。

首先可以看出来 + 号组成了一个阶梯形状，且 $s_{n,1}$ 与 $s_{1,m}$ 一定异号，否则答案一定为 $0$。（规定左上角为 $(1,1)$，右下角为 $(n,m)$。)

设 $a_i,b_i$ 分别表示 $x=i$ 与 $y=i$ 对应直线的权值，初始条件有 $a_1=b_1=0$（根本没有这条直线），那么有位置 $(x,y)$ 的权值为 $2(\sum_{i=1}^xa_i+\sum_{i=1}^yb_i)-(\sum_{i=1}^n a_i+\sum_{i=1}^m b_i)$。

编出一个粗暴的做法是简单的，直接从左下角开始 dp，注意到这个格子的权值是 $\sum_{i=1}^n a_i-\sum_{j=1}^m b_i$，而右上角的值是 $\sum_{i=1}^m b_i-\sum_{i=1}^n a_i$，也就是两者的权值是相反数。那么直接考虑枚举左下角的权值，然后按照 + 号形成的阶梯轮廓做 dp 即可。复杂度高达 $\mathcal{O}((n+m)k^4)$，没有写，不知道能不能过。10 s 感觉很有希望。

考虑换一种思路，注意到一个显然的性质是格子 $(x,y)$ 的权值严格大于其右下方的权值。那么最多只有 $n+m$ 个限制有用，这与最开始的阶梯状结论相互照应，只是这里更加细化了而已。一个 - 号的限制是有用的当且仅当其右下角无 - 号，类似地，一个 + 号的限制是有用的当且仅当其右下角无 + 号。

一个关键 Observation：所有有用的限制对应位置的权值全部在区间 $[-2k,2k]$ 内。这个是容易证明的，给张图就能明白。

图里面打钩的位置就是有用的限制。注意到从 + 号转移到 - 号时一定是先往右走若干步，然后向上走一步切换符号。在这个过程中，往右边走会让权值变大，往上走会让权值变小，所以起始位置的权值必定在 $[-2k,2k]$ 内，否则无法切换符号。从 - 号转移至 + 号同理。

最后一个问题就是左下角与右上角可能不是有用的限制，需要把这两段拼起来。这里可能出现两种情况。

其中打钩的位置分别是第一个/最后一个有用的限制。

那么现在需要再用一个 dp 去算出左上角/右上角对应权值的方案数。这个是容易算出的，拿第一个有用的限制来说，注意到往左下角靠的时候，数只会变大（如果是 + 号）/变小（如果是 - 号），用一个大小为 $k^2$ 的背包算一下就行。右上角同理。这里的复杂度直接写的话还是五方的（因为要枚举第一个有用的限制对应位置的权值）。优化是容易的，因为第一个限制对应的位置的权值是什么并不重要，只需要知道在往左下角靠的时候权值大了/小了多少对应的方案数即可，这个可以直接预处理，不需要每次重新算。

那么就做完了，时间复杂度 $\mathcal{O}(k^4+(n+m)k^3)$。

直接写五方（不预处理）比四方快/kx。

扔个没啥可读性的代码：https://www.luogu.com.cn/paste/1c43248e