Hint1
最暴力的 的算法你是否能优化到 ? 虽然仍然过不了本题,但对于下一步优化有很大的参考意义
Hint2
按位或 ( 按位与 , 都有这个性质)对于本题有什么比较有用的性质,能够优化到 来通过本题?
Solution
本题考察 按位或的性质 + 去重
对于本题有用的一个按位或性质如下:
满足 1 范围的 的二进制至多只有 位,而按位或则是对 位里面的每一位进行操作,对于两个数中的某一位来说,只要有一位有 或两个数的这一位都是 ,或的结果就是 ,从中我们就可以分析出,无限长的数组中所有的连续子数组(必须从第一个下标开始)按位或得到或的结果最多只有 个状态,最极限的情况也只是 的幂次方进行或,例如 ,我们连续异或了 次,每次其实只改了 位,但是总共也才 位, 不管你怎么改,最终你也只能改 位(这个过程是不可逆向的,改为 的位不可能再变成 ),而这个性质其实就是将复杂度 中的一个 优化到 的巧妙思想。
知道了按位或的性质,我们将利用dp的思想,巧妙利用到该性质。
对于 我们定义为结尾都必须包含第 个的所有连续子数组的或的结果(注意里面存储的是多个或的结果)
例如对于 个整数的数组 , , ,
那么答案其实就是 中所有的数全部放在一起,并且去重,然后计算其中小于k的个数。
转移规律就是 (注意 里面存储的是多个或的结果), 这是因为 是必须结尾包含 ,那么求 结尾必须包含 的所有连续子数组,就只需要把 或上 中所有存储的结果
上述思路看起来完全正确 , 但是我们会发现 中,随着 的增加其存储个数会急剧,因为根据转移规律来看,每次都会或上前面 中存储的所有数,如果不处理,时间会超时,内存也会爆炸
而根据我们得到的按位或性质, 中会有很多重复的东西,去重之后个数一定不会超过 个,因此求一次 时间接近 ,求完 时间复杂度就是 即可通过本题,下述代码中通过 容器去重,也可以 后 去重,也可以使用其他的去重算法。
C++代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 10);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<set<int>> mp(n + 10);
for (int i = 1; i <= n; i++) {
if (a[i] >= k)
continue;
mp[i].insert(a[i]);
if (i >= 2) {
for (auto j : mp[i - 1]) {
mp[i].insert((a[i] | j));
}
}
}
set<int> ans;
for (int i = 1; i <= n; i++) {
for (auto j : mp[i]) {
ans.insert(j);
}
}
int cnt = 0;
for (auto i : ans) {
if (i < k)
cnt++;
}
cout << cnt << endl;
}
signed main() {
int t = 1;
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cin>>t;
while (t--) solve();
return 0;
}