所谓 NOIp 模拟赛。
怎么会有 NOIp 模拟赛放 AT 银牌题呢哈哈。
A
暴力：枚举点对 \((c, s)\)，合法点对的贡献是 \((A - c + 1)\times (B - s + 1)\)。
对于 \(x = 1\) 的部分分，打表发现合法点对只有 \(c = s\) 的点对，那么贡献为
\[\begin{aligned} &\sum_{i = 1}^{\min(A, B)}(A - i + 1)(B - i + 1)\\ =&\sum_{i = 0}^{\min(A, B) - 1} (A - i)(B - i) \\ \end{aligned} \]令 \(C = \min(A, B) - 1\).
\[\begin{aligned} =&ABC - (A + B) * \sum_{i = 1}^{C}i +\sum_{i = 1}^{C}i^2 \end{aligned} \]模数是 \(2^{23}\)，自然数和建议开 __int128 直接乘，\(3\) 的逆元是 \(2796203\)。
然后暴力跑了几组数据发现 \(s \neq c\) 的合法点对数量好像不是很多，并且 \(s\) 很小。
考虑 \(s(c + x) | c(s + x)\) 化成 \(\dfrac{c(s + x)}{s(c + x)} = d\)，那么枚举 \(s\) 可以算出 \(c = \dfrac{dsx}{x + s - ds} \in [1, A]\)，这里由于要求 \(c \neq s\)，所以 \(d > 1\)，那么 \(s \le x\)，并且 \(d\in\left[\max\left(2, \dfrac{x + s}{sx + s}\right), \dfrac{x + s}{\frac{sx}{A} + s}\right]\)，枚举 \(s\) 和 \(d\)，差不多是调和级数 \(O(x \ln x)\)。
B
- 每个点集均满足以下两个条件之一：
- 该点集中的元素两两之间均有边。
- 该点集中的元素两两之间均没有边。
- 对于任意点 \(u\) 以及任意不包含 \(u\) 的点集 \(S\)，需满足以下两个条件之一：
- \(S\) 中的每个节点与 \(u\) 都有边。
- \(S\) 中的每个节点与 \(u\) 都没有边。
- 这些点集的并是点的全集。
那么两个点 \(x, y\) 在同一个集合里的充分条件是 \(\forall i \neq x \wedge i \neq y,w(x, i) = w(y, i)\)。
用异或哈希维护每个点相连的集合。
维护 \(hash_x\) 表示与 \(x\) 相连的点的权值异或和，那么两个点可以在一个集合满足 \(hash_x = hash_y\)（两点间无边）或 \(hash_x \oplus val_x = hash_y \oplus val_y\)（两点间有边）。
先算出所有哈希值。依次加入点，维护所有出现的哈希值，如果加入 \(x\) 时如果 \(hash_x\) 或 \(hash_x \oplus val_x\) 存在，说明 \(x\) 可以放到已有集合，不然 \(x\) 就要新开一个集合。
修改时先把 \(x, y\) 从维护的值里删去，修改后在加进去。
C,D
战绩可查 23/0/0，改不动。
对了这是 D。C 比 D 还抽象。
标签：12,hash,dfrac,sum,24.10,集合,aligned,neq From： https://www.cnblogs.com/KinNa-Sky/p/18460973