不难但是牛魔，随机数据大🐍。

A:

考虑若一个子矩形内有 $x$ 个 1 ，然后整个矩形一共有 $t$ 个 1 ，那么相似度为 $\frac{x}{t-x}$ 。

而计算一个固定的 $x$ 一共有多少个子矩形可以做到 $O\left(n^{3}\right)$ ，枚举左边界，右边界之后从上到下枚举下边界，计数合法的上边界个数即可。

若相似度为整数 $k$，则有 $\frac{x}{t-x}=k \Rightarrow x=\left(1-\frac{1}{1+k}\right) t$，说明 $(1+k) \mid t$。而数据随机生成，所以 $t$ 期望有 $\ln \left(\frac{1}{2} n^{2}\right)$ 个因数，只需枚举这些因数即可。

期望复杂度 $O\left(n^{3} \log n\right)$，期望得分 100 分。

B：

原题，前几天的反射容斥。

C：

暴力艹过了，但是题解看不懂。

考虑每次不暴力更新，而是枚举除掉的数是 $x$，那么能转移到的是一个区间，可以使用线段树维护区间最大值和最大值点来维护，考虑这样做的复杂度。

由于每次枚举除掉的数肯定不超过 $n / x$，所以最多 $\sum p(x) \min \{w, n / x\}$次线段树操作，如果把线段树的 $\log n$ 设为 100 的话，下图是两种算法的效率。

出题人试图分析了一下渐进复杂度，如下:

$$\begin{array}{l} \sum_{i=1}^{n} p(i) n / i \leq n \sum_{i=1}^{n} \frac{1}{i} \sum_{j} d_{0}\left(\left\lfloor\frac{i}{w^{j}}\right\rfloor\right) \\ \\ =\mathcal O\left(n \sum_{t} d_{0}(t) \sum_{k=1}^{\log _{w}(n / t)} \sum_{p=w^{k}}^{w^{k}(t+1)-1} 1 / p\right) \\ \\ =\mathcal O\left(n \sum_{t} d_{0}(t) \sum_{k=1}^{\log _{w}(n / t)} \log \left(\frac{w^{k} t(t+1)}{w^{k} t}\right)\right) \\ \\ =\mathcal O\left(n \sum_{t} d_{0}(t) \sum_{k=1}^{\log _{w}(n / t)} \log \left(\frac{t+1}{t}\right)\right) \\ \\ =\mathcal O\left(n \sum_{t} d_{0}(t) \log _{w}(n / t) \log (1+1 / t)\right) \\ \\ \left.=O\left(n \log _{w} n \sum_{i} \sum_{j=1}^{n / i} \log (1+1 / i j)\right)\right) \end{array}$$

由于 $\log (1+1 / x)=\mathcal O(1 / x)$，则

$$\left.=\mathcal O\left(n \log _{w} n \sum_{i} 1 / i \sum_{j=1}^{n / i} 1 / j\right)\right)=\mathcal O\left(n \log ^{3} n / \log w\right)$$

次线段树操作，总复杂度不超过 $\mathcal O\left(n \log ^{4} n / \log w\right)$，但似乎十分不满。

D：

非常好啊，还是贺的题解。

考虑把 2SAT 图建出来，缩点，此时缩完之后每一个点有一个与之对应的点，即为 $i n v_{u}$，这两个点的取值必须不同。

传递闭包之后，如果有 $u \rightarrow i n v_{u}$ ，或 $i n v_{u} \rightarrow u$ ，那么这一对点的取值就确定了，高处的那个为 0 ，低处的那个为 1 ，就可以忽略这对点了。

然后考虑在经过上述处理的图中进行暴搜。若在限制的意义下不连通 （即所有限制连边， $u$ 与 $i n v_{u}$ 连边形成的图不连通），则答案显然是各个连通块的乘积。

否则，考虑选择某一个点 $u$ ，枚举它是 0 还是 1。若是 0 ，那么所有 $i \rightarrow u$ 都是 0 ，所有 $i n v_{u} \rightarrow i$ 都是 1 ，若是 1 则反过来。

所以说，枚举了一个点的取值之后，会多确定能由它到达，或到达它的所有点。

我们试图选择这些点个数最大的那个，然后将其去掉递归，考虑分析复杂度，我们试图用度数来限制，肯定减少的总和要大于度数。

若所有点度数 $=0$，则都是孤立点，连通块分解后是 $\mathcal O(1)$ 的。

若所有点度数 $\leq 1$，则连通块大小不会超过 2 ，连通块分解后是 $\mathcal O(1)$ 的。

若所有点度数 $\leq 2$，则是一个个链和环，如果我们随机选择一个最大的点确定，则期望会被切分成两半，那么这么递归是 $\mathcal O(\operatorname{poly}(n))$ 的。

所以说，所有点度数至少是 3 ，也就是说复杂度是：

$$T(n)=\operatorname{poly}(n)+\max \{T(n-1)+T(n-4), T(n-2)+T(n-3)\}=\mathcal O\left(1.3803^{n}\right)$$

实际上，由于去掉了一些点导致其它点的度数进一步降低，加上随机化的部分，这个算法很难卡满，数据使用了一个每个点度数都为 3 的二分图以及一些类似的结构，大概能卡到 $2\times 10^{7}$ 次左右的递归。

如果没有随机化，则链和环的情况无法处理，这样的复杂度是：

$$T(n)=\operatorname{poly}(n)+\max \{T(n-1)+T(n-3), 2 T(n-2)\}=\mathcal O\left(1.415^{n}\right)$$

可能无法通过 $n \leq 60$ 。