P3773 Solution
\[\binom n m\bmod2=\binom{n\bmod2}{m\bmod2}\binom{n/2}{m/2}\bmod2 \]我们要让 \(\binom n m\bmod2\) 不为 \(0\)，也就是让右式的两项均不为 \(0\)。
考虑 \(\binom{n\bmod2}{m\bmod2}\)：\(n\bmod2\) 和 \(m\bmod2\) 的取值要么是 \(0\) 要么是 \(1\)，所以只有当 \(n\bmod2=0,m\bmod2=1\) 时这个式子为 \(0\)。
考虑 \(\binom{n/2}{m/2}\)：这相当于把 \(n,m\) 做了二进制拆分，拆分后 \(n,m\) 每位对应，只要出现 \(\binom 0 1\)，\(\binom n m\bmod2\) 的值就为 \(0\)。
这相当于把 \(n,m\) 当作两个集合来看，当且仅当 \(m\) 是 \(n\) 的子集时 \(\binom n m\bmod2\) 不为 \(0\)。即 \(n\ \text{bitand}\ m=m\)。
那么接下来就很简单了：由于每个数互不相同，设 \(pos_i\) 表示数 \(i\) 出现的位置，\(dp_i\) 表示从第 \(i\) 个数开始的答案。
我们倒过来枚举，枚举 \(a_i\) 的子集 \(j\)，如果 \(pos_j>i\) 那么 \(dp_i\gets dp_i+dp_{pos_j}\)。
代码
using namespace std;
const int N = 233333 + 10;
const int inf = ~0u >> 2;
const int p = 1e9 + 7;
int n,a[N],pos[N],dp[N],ans;
int main()
{
cin >> n;
for(int i = 1;i <= n;i++)
scanf("%d" , a + i),pos[ a[i] ] = i;
for(int i = n;i;i--)
{
dp[i] = 1; // 初值为一，假设单个元素也算
for(int j = a[i];j;j = a[i] & j - 1)
if(pos[j] > i)
dp[i] = ( dp[i] + dp[ pos[j] ] ) % p;
ans = ( ans + dp[i] ) % p;
}
cout << (ans - n + p) % p << endl; // 去除单个元素的贡献
return 0;
}