CF1085G Beautiful Matrix

· · 题解

I. CF1085G Beautiful Matrix

枚举所有字典序小于 a 的好矩阵 b 与 a 的 LCP 以及 b 的下一位的值。不妨设第一个不同位为 (i, j)。

枚举 b_{i, j}\in [1, a_{i, j}) 且 b_{i, j} 在 b_{i, 1} \sim b_{i, j - 1}（即 a_{i, 1}\sim a_{i, j - 1}）和 b_{i - 1, j}（即 a_{i - 1, j}）当中不能出现过，那么当前行接下来可以随便填，下面所有行也可以随便填，但要满足上下相邻两个数不同。

对于下面所有行，方案数很容易算，就是 n 阶错排数的 n - i 次方。但是对于当前行剩下 n - j 个元素，它们的填法受到 b_{i - 1, j + 1} \sim b_{i - 1, n}（即 a_{i - 1, j + 1} \sim a_{i - 1, n}）的限制，但不完全受到限制。具体地，求出有多少个数 v 使得 v 没有 在 b_{i, 1} \sim b_{i, j} 当中出现过，且在 b_{i - 1, j + 1} \sim b_{i + 1, n} 当中出现过，记作 L，那么相当于 n - j 阶排列限制了 L 个位置的错排的方案数，记作 f_{n - j, L}。

假设 f_{i, j} 已经求出，考虑优化 n ^ 3 的时间复杂度。因唯一不确定因素是 b_{i, j}，所以我们先求出没有出现在 b_{i, 1}\sim b_{i, j - 1} 且出现在 b_{i - 1, j + 1}\sim b_{i - 1, n} 的数的个数 L，b_{i, j} 对 L 的影响最多是当 b_{i, j} 出现在 b_{i - 1, j + 1}\sim b_{i - 1, n} 时将 L 减去 1。

因此，只需在 v\notin b_{i, 1} \sim b_{i, j - 1} 的前提下，维护存在多少个 v 使得 v\in b_{i - 1, j + 1}\sim b_{i - 1, n}，并且支持查询 \leq V 的 v 的个数。

用两个 BIT，一个维护前提下所有 v\in b_{i - 1, j + 1} \sim b_{i - 1, n}，另一个维护前提下所有 v。注意 b_{i, j} 不能等于 b_{i - 1, j}，所以若 b_{i - 1, j} < b_{i, j} 且 b_{i - 1, j} 没有在 b_{i, 1}\sim b_{i, j - 1} 出现过，还要减去 b_{i, j} = b_{i - 1, j} 产生的贡献。

接下来解决遗留问题 f_{i, j}。

当 i = j 时是经典错排，有递推式 f_{i, i} = (n - 1)(f_{i - 1} + f_{i - 2})。

否则 i > j，不妨设 i 这个位置没有限制。选择 j 个有限制的数当中某一个放到位置 i，得 j f_{i - 1, j - 1}；选择 i - j 个无限制的数当中某一个放到位置 i，得 (i - j)f_{i - 1, j}。

总时间复杂度 \mathcal{O}(n ^ 2\log n)。代码。