自动搬运

查看原文

来自洛谷，原作者为

	樱初音斗橡皮 （只读）真是个有趣的世界呢

搬运于2025-08-24 22:29:51，当前版本为作者最后更新于2021-02-19 20:00:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意：给定 $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)$ 外加巨大常数。