AGC035F Two Histograms

发表于 分类于 ， ， 阅读次数：

题意：有一个 的数组，初始时全 。

对每一行每一列，选出某个前缀将其 。显然，最终得到的矩阵中只会有 。

求最终能得到多少本质不同的矩阵。

，时限 。

题面相当于给了我们一个映射 ： 行列操作前缀长度 矩阵

我们只能直接知道行列操作的性质，直接统计矩阵较为困难。

分析映射计数无非两条路子，一是找条件，二是找反射。

一般而言，找反射（尤其是双射）较为困难，故先从必要条件入手。

先来研究如何构造结果相同的两个不同的操作序列，将操作序列集合化简。

设 为第 行选出的前缀长度， 为列。

不难发现，行列内部无影响，若要相同，只能一行一列之间替换，即：

。（一列伸长，一行缩短）

那不妨将所有能伸缩的位置都让行伸出来，一番调整之后可以在结果相同的前提下做到 即 （称之为不好的拐角）不存在。称这样的操作序列是好的。

我们成功地将操作序列集合化简了，即我们找到了映射：操作序列 好的操作序列

接下来就是分析映射：好的操作序列 矩阵

我们猜想这恰是一个双射，证明如下：

假设两组不同的好的操作序列为 ，且结果相同。

首先找出第一个不等的列 ，不妨设 。

考虑位置 ，显然，它只有可能为 。

则可以推出 。

同时，由好操作序列，推出 （否则这个行就可以进一步伸长）,所以 .

若 ，则有 ，矛盾。

若 ，由于 ，所以有

考虑位置 ，其被 覆盖了，但是没有被 覆盖。

又因为 （因为 是第一个不等的），列的覆盖情况相同，所以该位置必然不等。

通过这个双射，我们把问题转化成了：求好操作序列的个数。

考虑容斥，钦定 个不好的拐角，方案数为 :

为选出行列的方案数， 为行列匹配的方案数，构造不好的拐角的方案数恒为 ，后面的 是其余部分随意的方案数。

最终