bnds 8.27

P3120

朴素dp

\(dp_{i, j}\) 表示从 \((1, 1)\) 出发到 \((i, j)\) 的方案数，有 \(O(rc)\) 的转移，总时间复杂度 \(O(r^2c^2)\)，通过不了。

优化

设 \(sums\) 为 \((1, 1)\) 到 \((i - 1, j - 1)\) 的方案数和，\(sumd\) 为 \((1, 1)\) 到 \((i - 1, j - 1)\) 中，最后一个颜色为 \(a[i][j]\) 的方案数和，\(dp_{i, j}\) 即为 \(sums - sumd\)。

可以在枚举 \(j\) 的时候，把上一列的信息 \(O(r)\) 维护一下，时间复杂度 \(O(r^2 c)\)。

再优化

艹，十一 oj 过不了，因此在进行优化，因为这个转移限制很多，形式类似 cdq 分治，所以考虑对行进行分治，然后枚举列，考虑 \([L, mid)\) 对 \((mid, R]\) 的影响，同样用桶处理，再加上即可。

注意这题的分治顺序与正常的 cdq 分治不同，因为 \([L, mid)\) 对 \((mid, R]\) 有很大影响，所以先处理中间再处理下面。

P3121

ac 自动机，再开个栈标记一下。