Hint1

最暴力的 $O(n^3)$ 的算法你是否能优化到 $O(n^2)$ ？ 虽然仍然过不了本题,但对于下一步优化有很大的参考意义

Hint2

按位或 $|$ ( 按位与 $\&$ , $gcd$ 都有这个性质)对于本题有什么比较有用的性质,能够优化到 $O(nlog(n))$ 来通过本题？

Solution

本题考察 按位或的性质 + 去重

对于本题有用的一个按位或性质如下:

满足 1 $\leq$ $a[i]$ $\leq$ $1×10^9$ 范围的 $a_i$ 的二进制至多只有 $32$ 位,而按位或则是对 $32$ 位里面的每一位进行操作,对于两个数中的某一位来说,只要有一位有 $1$ 或两个数的这一位都是 $1$ ,或的结果就是 $1$ ,从中我们就可以分析出,无限长的数组中所有的连续子数组(必须从第一个下标开始)按位或得到或的结果最多只有 $32$ 个状态,最极限的情况也只是 $2$ 的幂次方进行或,例如 $1 \: | \: 2 \: , 1 \: | \: 2 \: | \: 4 \: , 1 \: | \: 2 \: | \: 4 | \: 8$ ,我们连续异或了 $3$ 次,每次其实只改了 $1$ 位,但是总共也才 $32$ 位, 不管你怎么改,最终你也只能改 $32$ 位(这个过程是不可逆向的,改为 $1$ 的位不可能再变成 $0$),而这个性质其实就是将复杂度 $O(n^2)$ 中的一个 $n$ 优化到 $log(n)$ 的巧妙思想。

知道了按位或的性质,我们将利用dp的思想,巧妙利用到该性质。

对于 $mp[i]$ 我们定义为结尾都必须包含第 $i$ 个的所有连续子数组的或的结果(注意里面存储的是多个或的结果)

例如对于 $3$ 个整数的数组 $1,2,4$ , $mp[1]=\{1\}$ , $mp[2]=\{2,1 \: | \: 2 \}$ , $mp[3]=\{4,2 \: | \: 4 , 1 \: | \: 2 \: | \: 4 \}$

那么答案其实就是 $mp[1],mp[2]...mp[n]$ 中所有的数全部放在一起,并且去重,然后计算其中小于k的个数。

转移规律就是 $mp[i]=a[i] \: | \: mp[i-1]$ (注意 $mp[i-1]$ 里面存储的是多个或的结果), 这是因为 $mp[i-1]$ 是必须结尾包含 $a[i-1]$ ，那么求 $mp[i]$ 结尾必须包含 $a[i]$ 的所有连续子数组,就只需要把 $a[i]$ 或上 $mp[i-1]$ 中所有存储的结果

上述思路看起来完全正确 , 但是我们会发现 $mp[i]$ 中,随着 $i$ 的增加其存储个数会急剧,因为根据转移规律来看,每次都会或上前面 $mp[i-1]$ 中存储的所有数,如果不处理,时间会超时,内存也会爆炸

而根据我们得到的按位或性质, $mp[i]$ 中会有很多重复的东西,去重之后个数一定不会超过 $32$ 个,因此求一次 $mp[i]$ 时间接近 $32$ ,求完$mp[1],mp[2]...mp[n]$ 时间复杂度就是 $O(32*n)$ 即可通过本题,下述代码中通过 $set$ 容器去重,也可以 $sort$ 后 $unique$ 去重,也可以使用其他的去重算法。

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;
}