Luogu

LOJ

分析

由 Lucas 定理可以推出，${n\choose m}\bmod 1\equiv{2}$ 当且仅当 $n \& m = m$。这样子很容易有一个 $\mathcal{O}(n^2)$ 的 DP。

为了方便，我们倒过来 DP，则要求上一个数是这一个数的子集，直接枚举子集转移即可。

复杂度是 $\mathcal{O}(3^{\log A})$ 的。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 233666 + 10;
const int mod = 1e9 + 7;

int n, a[N], dp[N];

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    int ans = 0;
    for (int i = n; i; --i) {
        dp[a[i]] = 1;
        for (int x = a[i] & (a[i] - 1); x; x = (x - 1) & a[i])
            dp[a[i]] = (dp[a[i]] + dp[x]) % mod;
        ans = (ans + dp[a[i]]) % mod;
    }
    printf("%d\n", (ans - n + mod) % mod);
    return 0;
}