「EZEC-6」分组
题目描述
给你 $n$ 个数，将它们分成任意组（可以不连续），将每个组内的数按位或，并将各组的结果累加，在保证其结果最小的情况下求最多分成的组数。
输入输出格式
输入格式
第一行输入一个正整数 $n$。
第二行输入 $n$ 个非负整数 $a_i$。
输出格式
一个正整数，最优解中最多分成的组数。
输入输出样例
输入样例 #1
6
1 1 4 5 1 4输出样例 #1
1输入样例 #2
7
1 9 1 9 8 1 0输出样例 #2
2输入样例 #3
8
1 9 2 6 0 8 1 7输出样例 #3
2输入样例 #4
9
3 1 4 1 5 9 2 6 5输出样例 #4
1输入样例 #5
9
9 9 8 2 4 4 3 5 3输出样例 #5
1输入样例 #6
6
1 2 3 4 8 12输出样例 #6
2说明
以下为各个样例的一种构造方案。
- $\{1,1,4,5,1,4\}$
- $\{1,9,1,9,8,1\},\{0\}$
- $\{1,9,2,6,8,1,7\},\{0\}$
- $\{3,1,4,1,5,9,2,6,5\}$
- $\{9,9,8,2,4,4,3,5,3\}$
- $\{1,2,3\},\{4,8,12\}$
对于样例 $6$ ，$\{1,2,3,4,8,12\}$ 也是一种最小化答案的方案，但是 $\{1,2,3\},\{4,8,12\}$ 分出的组数更多。
本题采用捆绑测试计分。
* Subtask $1$ ：$n\leq8$，$20$ 分。
* Subtask $2$ ：$n\leq10^3$，$20$ 分。
* Subtask $3$ ：$a_i\in\{0,1\}$，$5$ 分。
* Subtask $4$ ：$n=10^6$，且保证数据随机，$5$ 分。
* Subtask $5$ ：$n\leq10^6$，$30$ 分。
* Subtask $6$ ：$n\leq10^7$，$20$ 分。
对于所有数据，$0\leq a_i\leq10^{18}$，$1\leq n\leq10^7$。
如果你不知道什么是按位或，请[点击这里](https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E6%88%96)。
本题自动开启O2优化。
本题提供读入优化方式。
使用 `read(x);` 读入一个任意的整型 `x` 等价于 `scanf("%d", &x);`其中可以将 `%d` 自动识别为对应类型。
```cpp
#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;
}
```