BZOJ3456 城市规划 – 2

题意

给出 $n$ ,请求出点数为 $n$ 的简单无向联通图个数

题解

之前这篇面讲了多项式对数的做法
这里讲个分治 NTT 的方法
设 $f_n$ 表示大小为 $n$ 的图的方案,那么枚举 1 所在的连通块大小,有转移:
$$
\begin{eqnarray}
f_i&=&2^{{i\choose 2}}-\sum_{j=1}^{i-1}{i-1\choose j-1}\cdot 2^{{i-j\choose 2}}\cdot f_j\\
&=&2^{{i\choose 2}}-(i-1)!\sum_{j=1}^{i-1}\frac{f_j}{(j-1)!}\cdot \frac{2^{{i-j\choose 2}}}{(i-j)!}
\end{eqnarray}
$$
继续阅读

BZOJ4237 稻草人

题意

给出 $n,(n\leq 2\times 10^5)$ 个点的坐标,求可以构成矩形左下角和右上角并且矩形中不包含任何其他点的点对个数

题解

分治+单调性
看题解都有点难看懂,但是看程序一下就看得懂
题解理性愉悦一下
首先按照 $x$ 坐标划分然后分治,考虑处理完两个子区间后怎么求当前区间答案
发现对于某个点 $(x,y)$ 我们找到最小的 $y_0$ 使得点 $(x_0,y_0)$ 满足 $x_0>x,y_0>y$ (对左边区间中的点考虑),那么该点在右边的合法配对点坐标只可能满足 $y< y_1< y_0$
那么我们将两个区间分别按照 $y$ 坐标排序,然后依次处理左边,对左边每个点计算右边有多少个点能和它配对 继续阅读