Description：

给一个长度为 $n$ 的数列 $a_1, a_2, \cdots , a_n$ ，问有多少个长度大于等于 $2$ 的不上升的子序列满足： $$ \prod_{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \mod 2> 0 $$ $1\leqslant n\leqslant211985, 1\leqslant a_i\leqslant233333,$ 保证 $a_i$ 互不相同。

Solution：

发现那个式子的含义就是每个组合数都是奇数。

那么一个组合数是奇数当且仅当 $n\&m=m$ ，也就是说选出来的子序列后面一个必须是前一个的子集，这样也就满足了不上升的条件，那么就可以对于每个数暴力枚举他的子集，因为有互不相同的条件，所以由子集枚举的复杂度得复杂度是 $3^{\log_2 n}$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 240010

int a[MAXN];

int pos[MAXN];

int f[MAXN];

#define MOD 1000000007

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)pos[a[i]] = i;

	for(int i = n;i >= 1;--i)

	{

		f[i] = 1;

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

		{

			if(pos[j] > i)

			{

				f[i] = (f[i] + f[pos[j]]) % MOD;

			}

		}

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)ans = (ans + f[i]) % MOD;

	cout << (ans - n + MOD) % MOD << endl;

	return 0;

}