AGC041F Histogram Rooks

题意：有一个 行的棋盘，第 行的长度为 ，左侧对齐。

该棋盘上放置“車”棋子，若一个格子和某个“車”同行或同列，且之间都是棋盘，则称该格子被覆盖。

求将该棋盘完全覆盖的放置方案数。

答案对 取模，，时限 。

---

AT 题目总是让人一看就很想知道答案，但是想半分钟就会发现根本不可做。

市面上的题解都比较意识流，看了半天才看懂，这里整理一个详细一点的……

---

考虑容斥，选（钦定） 个格子没有被覆盖，容斥系数为 。

此时对于某个还能放置車的格子，方案数就是 。

这个做法虽然很直观易懂，但是还没有利用题目的任何性质。考虑对“不可放置”这一条件进行化简。

不难发现，由于行总是连续的，若某一行选了一个格子，则这一整行都不能放置車。

枚举不能放置車的行集合 （不是钦定）。这样，就只需要再考虑列的约束，行列能独立了。

所以，对于每个独立的部分，即列上的一个极长连续段，计算出贡献，然后乘起来即可。

若列连续段长度为 且有 个格子在 中，贡献有如下两种：

• ① 没有格子被选，则所有不在 中的格子都能放置，方案数为 。

• ② 枚举选格子的个数，贡献为 。

但这个做法是错误的，因为不能保证 中的每行都至少有一个点被选。

---

那就……再容斥！

钦定不能选格子的行集合 ，容斥系数是 。

若列连续段中有 个格子在 中，则还能选的格子个数只剩下 ，二类贡献变为 。

现在正确性有保证了，然而枚举 的复杂度太高，所以接下来寻找反射。

不难发现，一个列连续段最终的贡献只与 有关。（ 要么 要么 ）

前面的做法指出了映射 “ 各个连续段 ”，现在我们反过来，对某个贡献已经确定的局面，寻找所有可能的 的 的和。

坏消息是，在统计 时，列连续段之间不再是独立的。也就是说，该连续段计数的不同的 对其他连续段有不同的影响，所以不能简单地乘法原理了事。

具体地，影响的方式如下：

观察棋盘的形状，将其剖分成笛卡尔树的形式，如图：（图是蒯 @Itst 神的）

我们只关心 。

在某个确定的 局面中，有如下显然事实：

红色部分的某一列在 中的行的数量 绿色部分在 中的行的数量 蓝色部分在 中的行的数量 第四行是否在 内。

红色部分的某一列的 绿色部分的 蓝色部分的 第四行的

这启发我们在笛卡尔树上做树形 。

---

设 为：对笛卡尔树的节点 ，其 为给定情况，所有 的 且乘上儿子所有贡献的和。

转移时， 那一维是背包，而 那一维是 。

对于右侧没东西的行，可以看作特殊的儿子。

复杂度为树上背包的复杂度，即 。

求出 后，计算出自己一列的贡献，再 pow 一下列数，就能得到自己的贡献。

若每次都 pow，复杂度可以达到 。但不难发现本质不同的贡献只有 种， 预处理幂即可。