题解 - T167788 画矩形

· · 题解

题目大意：给定 n\times m 网格以及 q 个 1\times 1 的障碍物，问能画出多少个周长不大于 k 的、四边平行于坐标轴的矩形。

数据范围：1\le n,m\le 10^9，4\le k\le 10^9，1\le q\le 20。

解答：

看到“不包含障碍点”而 q 又很小，容易想到容斥计算贡献。

设仅考虑障碍物集合 S 时方案数 f_S，则：

Ans=\sum_S f_S(-1)^{|S|}

情况 1. S 非空

设障碍物中 x 和 y 坐标的最小、最大值分别是 x_m,y_m 和 x_M,y_M。

设 g(x_0,y_0) 表示不考虑网格边界且 x_M-x_m+1=x_0,y_M-y_m+1=y_0 的答案，则：

g(x_0,y_0)=\sum_{x\ge x_0}\sum_{y\ge y_0}[x+y\le \dfrac k 2](x-x_0+1)(y-y_0+1) =\sum_{x\ge 1}\sum_{y\ge 1}[x+x_0-1+y+y_0-1\le \dfrac k 2]xy

设 s=\dfrac k 2 + 2-x_0-y_0，则：

g(x_0,y_0)=\sum_{x=1}^{s}x\sum_{y=1}^{s-x}y =\sum_{x=1}^sx\big(\dfrac{(s-x)(s-x+1)}{2}\big)

可以通过 \sum_{x=1}^s x、\sum_{x=1}^sx^2 和 \sum_{x=1}^sx^3 的公式 O(1) 算出。

那么考虑到网格的边界情况又怎么求呢？很简单，对网格的四边进行容斥即可。

具体地，设 h_{S,T} 表示仅考虑障碍物集合 S、边界集合 T 时的答案，则 f_S=\sum_Th_{S,T}(-1)^{T}。

如何计算 h？一个简单的办法是：在考虑边界 x=0 时把 x_m 强制设为 0，在考虑边界 x=n 时把 x_M 强制设为 n+1，可以想象在原有的格子外加了一格并强制要求包含此格。

情况 2. S 为空

此时，答案为：

f_S=\sum_{x=1}^n\sum_{y=1}^m[x+y\le \dfrac k 2](x_0-x+1)(y_0-y+1) =\sum_{x=1}^{\min(n,\frac k 2)}(x_0-x+1)\sum_{y=1}^{\min(m,\frac k 2-x)}(y_0-y+1)

根据 m 与 \dfrac k 2-x 的大小关系分段考虑即可。每一段都可以 O(1) 求出。

总复杂度 O(2^q) 外加巨大常数。