专栏文章

AGC041F

llsj2009Isj2OO9
AT_agc041_f题解参与者 12已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@miqmc5zb
此快照首次捕获于
2025/12/04 07:08
3 个月前
此快照最后确认于
2025/12/04 07:08
3 个月前
查看原文

Preface

非常 Educational 的题！
虽然感觉独立做出了大半，但还是感觉这个题很深刻。

Description

给定一个直方图，其中第 ii 列高度为 aia_i，可以往上面放若干个車，每个車会占领其 所在列上的所有格子 和 向左、向右延申直到碰到边界的所有格子。
求有多少种放車的方案使得每个位置都会被 至少一个 車占领。
1≤ai≤n≤4001\le a_i\le n\le 400。
Bonus：1≤n≤30001\le n\le 3000，1≤ai≤1091\le a_i\le 10^9。

Solution

Part 1

事实上相当于每个位置上有一个限制，刻画为：所在行的连续段和所在列至少有一个車。
则答案就是对于满足每个限制的方案集合 交集，也就是得满足所有限制。
比较套路地，钦定 ii 个限制 违反，其于限制 不进行强制要求，只需要将此情况的方案数乘上 (−1)i(-1)^i 再求和即可。
容斥系数推导较为经典，这里不赘述。
若枚举所有 钦定违反限制的格子集合 SS，是容易快速计算出此情况下的方案数的，即可做到 O~(2∑ai)\widetilde{\mathcal{O}}(2^{\sum a_i}) 复杂度。

Part 2

一个关键观察是：列是连续的。
所以考虑 枚举（注意不是钦定！！这会在全文的最后有解释）哪几列 存在我们钦定违反限制的格子。记我们枚举的列集合为 SS。
这里 枚举 的含义是：任意 x∈Sx\in S 的列均存在钦定违反限制格子，任意 x∉Sx\notin S 的列均不存在钦定违反限制的格子。
则每一行，会分成若干连续段 [l1,r1],[l2,r2],⋯ ,[lk,rk][l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]，对于每一个连续段考虑其是否存在不合法格子。
  • 不存在：则任意 x∉Sx\notin S 的列均可以放車，对答案贡献即为 2∣[li,ri]∣−∣[li,ri]∩S∣2^{|[l_i,r_i]|-|[l_i,r_i]\cap S|}。
  • 存在：则该连续段内不可以放車，且需在 [li,ri]∩S[l_i,r_i]\cap S 内选择一 非空 子集 TT 钦定 TT 中所有格子违反限制，即对答案贡献为 ∑∅≠T⊆([li,ri]∩S)(−1)∣T∣=(∑i≥0(∣[li,ri]∩S∣i)(−1)i)−1=−[[li,ri]∩S≠∅]\sum\limits_{\emptyset\ne T\subseteq \left([l_i,r_i]\cap S\right)} (-1)^{|T|}=\left(\sum\limits_{i\ge 0} \binom{|[l_i,r_i]\cap S|}{i}(-1)^i\right)-1=-[[l_i,r_i]\cap S\ne\emptyset]。
记 t=∣[li,ri]∩S∣t=|[l_i,r_i]\cap S|，则该连续段对答案贡献为 2∣[li,ri]∣−x−[x≠0]2^{|[l_i,r_i]|-x}-[x\ne 0]。这里的贡献为 乘法。
然而你注意到这样子其实不太对：
  • 任意 x∈Sx\in S 的列 均存在 钦定违反限制格子。
  • 任意 x∉Sx\notin S 的列 均不存在 钦定违反限制的格子。
我们并没有保证前者的每一列都存在违反限制的格子。
但这仔细看这句话：任意 x∈Sx\in S 的列 均存在 钦定违反限制格子。
这其实对于每个 x∈Sx\in S 都是一个限制，我们求的就是对于每个满足限制的方案集合 交集 的大小。
这其实和我们最开始的问题形式上一模一样！！！
同样考虑容斥，钦定一个列集合 T⊆ST\subseteq S，令任意 x∈Tx\in T 的列 xx 违反限制，也就是其中 没有 违反限制的格子（但仍然 不能放車，否则这和我们枚举集合 SS 的根本冲突了！）。同样，带 (−1)∣T∣(-1)^{|T|} 的容斥系数即可。
则原来的贡献改写成如下形式：
  • 不存在：则任意 x∉Sx\notin S 的列均可以放車，对答案贡献即为 2∣[li,ri]∣−∣[li,ri]∩S∣2^{|[l_i,r_i]|-|[l_i,r_i]\cap S|}。
  • 存在：则该连续段内不可以放車，且需在 [li,ri]∩(S∖T)[l_i,r_i]\cap (S\setminus T) 内选择一 非空 子集 T′T' 钦定 T′T' 中所有格子违反限制，即对答案贡献为 =−[[li,ri]∩(S∖T)≠∅]=-[[l_i,r_i]\cap (S\setminus T)\ne\emptyset]。
这样子暴力做我们也就获得了一个 O~(3n)\widetilde{\mathcal{O}}(3^n) 的做法。

Part 3

进一步优化：我们考虑将整个直方图 剖分。
这也就是我们上面说的每一行的连续段，当然我们有把这种“比较厚”的连续段缩在了一大块。
如何比较好的刻画这个东西？广义笛卡尔树（这个东西在网上好像没有什么 blog，但确实是有听过这样子的一个名字的）。
普通的笛卡尔树是一个二叉树，且仅在对 排列 建树时有比较好的定义，否则如果当前 存在多个最值，取谁为根是要打一个问号的。
广义笛卡尔树给出了比较好的解决方法。广义笛卡尔树上分 方点 和 圆点，前者刻画为一个 区间，后者为一个 单独的点。
下面给出一个例子可能可以比较好的解释：
  • 求序列 1,1,4,5,1,41,1,4,5,1,4 的广义笛卡尔树。
这应该就很清晰了。
注意到对于一个行段算贡献的时候我们其实只关心 ∣S∩[li,ri]∣|S\cap[l_i,r_i]| 的值和 [(S∖T)∩[li,ri]=∅][(S\setminus T)\cap[l_i,r_i]=\emptyset] 的值。
考虑在 aa 序列的广义笛卡尔树上 dp。更清晰的，对于一个广义笛卡尔树上的方点（这对应一个连续段）的区间 [li,ri][l_i,r_i] 我们 暂且先仅保留 SS 在 [li,ri][l_i,r_i] 中的部分，记录 ∣S∣|S|，以及当前是否有 S∖T=∅⇒S=TS\setminus T=\emptyset\Rightarrow S=T。
合并两个儿子时对于 ∣S∣|S| 做加法，[S=T][S=T] 取与即可。
即：
fu,i,p1×fv,j,p2→fu,i+j,p1and⁡p2′f_{u,i,p_1}\times f_{v,j,p_2} \to f'_{u,i+j,p_1\operatorname{and}p_2}
进行完子树内的合并后考虑 连续段内产生的贡献：
fu,i,p×(2∣[lu,ru]∣−i−(1−p))bu→fu,i,pf_{u,i,p}\times\left(2^{|[l_u,r_u]|-i}-(1-p)\right)^{b_u}\to f_{u,i,p}
其中 bub_u 为该方点和其父亲节点 aa 值之差，也就是该连续段的 厚度。
核心在于：对于一个节点 uu 的两个儿子，其对应区间无交。
圆点有何用？初始化 (−1)∣T∣(-1)^{|T|} 的系数。
fu,0,1=fu,1,0=1fu,1,1=−1\begin{aligned} & f_{u,0,1}=f_{u,1,0}=1\\ & f_{u,1,1}=-1 \end{aligned}
由于转移需要快速幂，所以复杂度即为 O(n2log⁡V)\mathcal{O}(n^2\log{V})。

Code

Submission Link。

Others

这时候再来回头看看为啥 SS 是 枚举。
钦定 表示为强制令 SS 中的每一列均存在违反限制的格子，而不在 SS 中的列是不进行约束的（这样就导致了 钦定 往往带有额外的容斥系数）。
但其实注意到 不进行约束 的方案数是很难计算的，因为你无法很好地计算 既可以有违反格子也可以无违反格子 的方案数。
所以我们强制钦定不在 SS 中的列均不能有违反的格子，这样子也就能快速算方案数了。

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...