NOIP 模拟赛：2024-10-15

FLYlai / 2024-10-21 / 原文

T1：

每个连通块都删成树。

T2：

$S(x)\cap S(y)=S(lcm(x,y))$，而 $S(\ge 60)$ 里只会有 $1$ 这个数，因为答案保证 $\le 10^{17}$。

同时注意到若 $n_i|n_j$，那 $n_j$ 没必要存在。

直接搜索 + 容斥，如果当前 $lcm\ge 60$ 就退出。

T3：

T4：

按位与：从高位到低位扫描，若当前位可以是 $1$，令当前位是 $1$，只保留当前位是 $1$ 的数在数组里。

按位异或：01-Trie 经典例题。

按位或：同样是贪心。但是问题在于如果遇到 $1$ 位无法减少可能性。

假设现在已经枚举了 $a_i$，要求和 $a_i$ 按位或的最大值。设 $a_i$ 中 $0$ 的位的集合是 $Zero$。

举一个例子：$Zero=\{9,4,1\}$。那么我们先判断是否存在 $\{9\}$ 是 $1$ 的数，比如存在；再判断是否存在 $\{9,4\}$ 是 $1$ 的数，比如不存在；然后判断 $\{9,1\}$ …… 如此判断下去。

我们自然想到要预处理出 $f[S]$ 表示使得 $S$ 中位为 $1$ （其他位随便）的数个数。如果成功求出，判断变成 $O(1)$ 的，而且方案数也好求了。
但是如果直接求，是 $O(n\cdot 2^{23})$ 的，不能接受。

设 $a_i$ 中 $1$ 位集合是 $A_i$，$p[T]$ 表示 $A_t=T$ 的 $t$ 个数。那么 $f[S]=\sum_{S\subseteq T}p[T]$，可以 SOSDP。

首先 $p[T]$ 显然好求。设 $g[i][S]$ 表示所有 $30\sim i$ 位都与 $S$ 相同（$i-1\sim 0$ 位随便），包含 $S$ 的集合 $T$，$p[T]$ 的和。

考虑转移，$g[0][S]=p[S]$。若 $S$ 的 $i-1$ 位是 $1$，$g[i][S]=g[i-1][S]$，因为要使得 $S\subseteq T$，又 $S$ 第 $i-1$ 位是 $1$，显然 $T$ 的第 $i-1$ 位也应该是 $1$，也就是和 $S$ 的第 $i-1$ 位相等了。
若 $S$ 的 $i-1$ 位是 $0$，此时 $T$ 的 $i-1$ 位可以是 $0/1$。若是 $0$，$g[i][S]\leftarrow g[i-1][S]$；若是 $1$，$g[i][S]\leftarrow g[i-1][S+2^{i-1}]$。因此可以 $O(23\cdot 2^{23})$ 递推出 $g[i][S]$。