P7384题解
MasterArcherSkeleton
·
·
题解
提前说的话
本文中，所有的 \mid 符号都表示按位或，所有的 \& 符号都表示按位与。若有特例，会特殊说明。
题意简化
题目中的【题目描述】部分已经足够简化了，这里就不再简化题意了，题目 P7384 「EZEC-6」分组。
暴力与特殊数据简述（Subtask 1 & Subtask 3 & Subtask 4，30pts）
暴力（Subtask 1，20pts）
如果直接枚举组数再分组最后计算的话，时间复杂度将会达到惊人的 \Omicron(n \cdot n^n \cdot n) = \Omicron(n^{n + 2})，连 n \le 8 的数据都过不去（如果能过，那就是数据水，因为 8^{10} = 1073741824，一看就不行）。优化的话，就直接枚举组号并用一个数组和一个变量分别去记录每组的元素个数和总组数，时间复杂度优化为 \Omicron(n\cdot n^n) = \Omicron(n^{n+1})。这会应该能过了（8^9 = 134217728，加一点剪枝（不加应该也行）应该能过，说应该是因为我觉得没意义，所以没试过）。
特殊数据（Subtask 3 & Subtask 4，10pts）
Subtask 3（5pts）
注意到，第三组测试数据：a_i \in \{0,1\}，稍加思索即可知：将每一个 0 单独分一组，所有的 1 分一组。那就输出：0 的个数加 1——对吗？错！一定要特判一下没有 1 的情况，没有 1 时，是不能加 1 的，加 1 是表示加上放 1 的那一组，1 都没有，还怎么加？当然，不排除数据水卡过的情况（我没试过，不知道能不能过），但是我们不能因为数据水就认为自己过了。好吧，反正这个数据的分也是能拿到的。
Subtask 4（5pts）
注意到，第四组测试数据：n = 10^6，且保证数据随机。这就意味着，两个数大概率不会重复。不过等一会儿再说，先要证明一个引理。
引理 1
是什么
对于任何两个非负整数 x、y，都有 x + y \ge x \mid y。并且这个不等式当且仅当 x \text{ } \& \text{ } y = 0 时取等。
如何证明
先把 x,y 的二进制形式表示出来（令 x,y 的二进制分别为 X 序列和 Y 序列）。即：存在唯一的一种表示，使：\sum_{i = 0}^{\infty}(X_i \cdot 2^i) = x，\sum_{i = 0}^{\infty}(Y_i \cdot 2^i)（其中，X_i,Y_i \in \{0,1\}），则 X 序列和 Y 序列分别是 x 与 y 的二进制表示序列。
再定义两个序列 V 和 W，令 V_i = X_i + Y_i，W_i = X_i \mid Y_i，则不难发现：
\begin{cases}
V_i = W_i & X_i \text{ } \& \text{ } Y_i = 0 \\
V_i = W_i + 1 & X_i \text{ } \& \text{ } Y_i = 1 \\
\end{cases}
即：$\sum_{i = 0}^{\infty} (V_i \cdot 2^i) \ge \sum_{i = 0}^{\infty} (W_i \cdot 2^i)$。
又因为：
$$
\begin{aligned}
\sum_{i = 0}^{\infty} (V_i \cdot 2^i) &= \sum_{i = 0}^{\infty} ((X_i + Y_i) \cdot 2^i) \\
&= (\sum_{i = 0}^{\infty} (X_i \cdot 2^i)) + (\sum_{i = 0}^{\infty} (Y_i \cdot 2^i)) \\
&= x + y
\end{aligned}
$$
以及：
$$
\begin{aligned}
\sum_{i = 0}^{\infty} (W_i \cdot 2^i) &= \sum_{i = 0}^{\infty} ((X_i \mid Y_i) \cdot 2^i) \\
&= x \mid y
\end{aligned}
$$
所以：$x + y \ge x \mid y$。
不难发现：这个不等式当且仅当 $\forall k \in \N, V_k= W_k$ 时取等。
即：这个不等式当且仅当 $\forall k \in \N, X_k \text{ } \& \text{ } Y_k = 0$ 时取等。
即：这个不等式当且仅当 $x \text{ } \& \text{ } y = 0$ 时取等。
引理证明完了，那这个引理又什么用呢？没用。注意到“保证数据随机”，所以不存在两个相同的的数同时都在原数组里。还有，令两个组中每组的所有元素按位或起来的结果分别为：$x$、$y$。
$\because a_i \ge 0$，$\therefore x, y \ge 0$。
注意到，若将两个组进行合并，组数会减一，那结果会发生什么变化呢？若结果比原来更小，则答案会更优。即：当且仅当 $x \mid y < x + y$ 时，这两个组才有必要合并。当然，这种形式我们肯定不想要。这个时候就用到了引理 1。$x \mid y < x + y$ 可以转变成 $x \text{ } \& \text{ } y \ne 0$。即：$x \text{ } \& \text{ } y > 0$（这一步是因为 $x,y \in \N$）。所以，当且仅当 $x \text{ } \& \text{ } y > 0$ 时，这两个组才有必要合并。然而此时的 $n$ 很大，所以即使出现了 $k$ 组不重复的的无序数对 $(u_i,v_i)(1 \le i \le k, 1 \le u_i,v_i \le n)$，使 $\forall 1 \le i \le k, a_{u_i} \text{ } \& \text{ } a_{v_i} = 0$，它们也总会合并到其它组中。然后紧接着导致这些组的合并，它们最终也会被合并。——除了 $0$ ！！！你可以特判一下，但是出现 $0$ 的几率也同样很小（当然，也有可能出现 $0$，~但是数据中确实没有~）。反正现在至少能够拿到 Subtask 4 的分。
# 高分到正解
在 Subtask 4 的分析中，几乎都已经接近正解了。思路几乎就是合并加特判 $0$（因为 $0$ 很特殊，它们需要每一个数一个组）。但是，如何合并呢？我们立刻就想到了——并查集！但是，计算一下时间复杂度吧：$\Omicron(n log a)$。超时了，还是超时了！最后一个 Subtask TLE 了！那么到底该怎么办呢？我们想到，根本没有必要去用并查集。只需要用最低二进制位编号作为下标再去用双层循环去合并即可。在输入时，将 $a_i$ 加入编号为 $lowbit(a_i)$ 的组（将数组里的结果按位或上 $a_i$，组的编号从 $0$ 开始，若 $a_i = 0$，则将答案加一，不加入任何组）。其中，$lowbit(x)$ 表示一个整数 $k$，使 $2^k \parallel x$（特殊说明：如果 $a$ 和 $b$ 为整数且 $a \ne 0$，我们说 $a$ 整除 $b$ 是指存在整数 $c$ 使得 $b = ac$。如果 $a$ 整除 $b$，我们还称 $a$ 是 $b$ 的一个因子，且称 $b$ 是 $a$ 的倍数。如果 $a$ 整除 $b$，则将其记为 $a \mid b$（这里的 $\mid$ 表示整除），如果 $a$ 不能整除 $b$，则记其为 $a \nmid b$。……$p^a \parallel n$ 表示恰整除，即：$p^a \mid n$ 但是 $p^{a+1} \nmid n$。（摘自（美）Kenneth H.Rosen著的《初等数论及其应用》（原书第6版）））。在加入完后，用 $i$ 来循环（注意到 $2^{59} = 576460752303423488 < 10^{18}$，而$2^{60} = 1152921504606846976 > 10^{18}$，所以编号范围为 $0$ ~ $59$）。定义 $f$ 数组来完成这一点（$f_{lowbit(a_i)}$ = $f_{lowbit(a_i)} \mid a_i(a_i > 0)$）。之后找到第一个 $j(i < j \le 59)$（如果存在的话），使：$f_i \mid f_j < f_i + f_j$，然后让 $f_j$ 按位或上 $f_i$，此时 $f_i$ 这一组就被全部加入到了 $f_j$，所以让 $f_i = 0$（方便统计答案），然后如果 $f_i > 0$，则这一组无法合并，将答案加一，最后输出即可。
# 代码
大致思路就是这样，不过在实现的过程中会有一些不同。在计算 lowbit 函数时，可以使用循环，也可以使用 log2 函数和位运算（`int(log2(x & (-x)))`）。不过第一种的时间复杂度要是被卡到了极限的 $\Omicron(60n)$ 的话，可能会有些危险。我个人倾向于第二种实现方式。不多说了，上代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
r=0;bool w=0; char ch=getchar();
while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
r=w?-r:r;
}
int n, x, ans, f[60];
signed main()//因为已经将“long long”define成“int”了，而 main() 主函数不能返回 long long，所以此处要写 signed。
{
read(n);
for(int i = 1; i <= n; i ++) {
read(x);
if(!x) {
++ans;
continue;
}
f[signed(log2(x & (-x)))] |= x;//log2() 函数的返回值类型使其不能称为 f[] 数组的下标需要将其变成 int 类型。同上，这里需要写成“signed”。
}
for(int i = 0; i < 60; i ++) {
for(int j = i + 1; j < 60; j ++) {
if(f[i] & f[j]) {
f[j] |= f[i];
f[i] &= 0;
break;
}
}
if(f[i]) ++ans;
}
cout << ans;
return 0;
}
``````
# 数据通过情况
[评测记录](https://www.luogu.com.cn/record/198392508)
# 最后的话
__同样的，还是提醒大家，不要抄代码！__ 理解了再写。还有，如果文中有漏洞，请大家指正。代码仅供参考，不喜勿喷。写篇文章不容易，可否来个赞？