1
4
2
15
3
7
4
3
5
1

1
11

我们可以尝试使用 dp 来解决子序列问题．

定义 dp[i] 表示以第 $i$ 个数结尾能够有多少满足要求的子序列．由于题意要求所有组合数的乘积模 2 大于 0，那就是要求所有组合数都是奇数．

转移方程为：

可以使用递推公式快速算出组合数．

这样能够拿到 40 pts．当 $a_i$ 到二十万的数据规模就无法处理了，那该怎么办呢？

Lucas 定理：

当 $p=2$ 时，

将 $\binom{\lfloor x/2\rfloor}{\lfloor y/2\rfloor}$ 拆解，可得：

像这样拆解，最终可得：

其中，$x_i,y_1$ 分别表示 $x,y$ 中二进制表示的第 $i$ 位．

当且仅当 $x_i=0,y_i=1$ 时，$\binom{x_i}{y_i}=0$，故 $\binom{x}{y}\bmod 2=1$ 等价于 $\forall i,x_i=0\Rightarrow y_i=0$，即位运算中 $x\wedge y=y$． 其实就是 $x$ 是 $y$ 二进制中的子集．

因此，在 dp 时，尝试子集枚举．具体来说，遍历到 $a[i]$ 时，先将 $f[i]$ 增加 1，表示 $a[i]$ 单独成一组．再枚举 $a[i]$ 的所有子集 $k$，若 $k$ 在后面出现过（设其处于 $a[j]$），则说明 $f[i]$ 可以转移到 $f[j]$，将 $f[i]$ 贡献给 $f[j]$．

子集枚举可以使用下面的代码：

1
for (int j = (a[i] - 1) & a[i]; j > 0; j = (j - 1) & a[i])

请注意：由于题目中所要求的序列长度大于等于 2，因此最终答案需要减去 $n$ 个长度为 1 的序列．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int N = 240000;
5
const int MOD = 1e9 + 7;
6

7
int n, a[N], id[N], f[N], ans;
8

9
signed main() {
10
    cin >> n;
11
    for (int i = 1; i <= n; i++) {
12
        cin >> a[i];
13
        id[a[i]] = i;
14
    }
15
    for (int i = 1; i <= n; i++) {
16
        (f[i] += 1) %= MOD;
17
        (ans += f[i]) %= MOD;
18
        for (int j = (a[i] - 1) & a[i]; j > 0; j = (j - 1) & a[i]) {
19
            if (id[j] > i)
20
                (f[id[j]] += f[i]) %= MOD;
21
        }
22
    }
23
    cout << ans - n;
24
    return 0;
25
}