[COTS 2018] 仲裁 Arbitraža

· · 题解

答辩 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