Description：

给出一个序列 $a$ ，求所有 $\prod\binom{b_k}{b_{k+1}}\bmod 2=1$ 的子序列 $b$ 的个数。

$1\leqslant n\leqslant 10^5$

Solution：

不难发现是 $CTSC$ 吉夫特加强版。

首先根据卢卡斯定理： $$ \binom nm\bmod2=\binom{n/2}{m/2}\bmod2\times \binom{n\bmod 2}{m\bmod2}\bmod2 $$ 然后就会发现，这样的子序列满足后一个是前一个的子集，于是可以暴力 $DP$ ，每次枚举子集转移，但是由于这题不保证数字两两不同，因此复杂度是 $O(n2^n)$ 的。

考虑值域分块，也就是设 $f[i][j]$ 表示前 $9$ 位是 $i$ 的子集，后 $9$ 位是 $j$ 的方案数，然后就会发现枚举量只有 $2^9$ 可以通过。时间复杂度 $O(2^9n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

#define N 200010

int a[MAXN];

int f[1 << 9][1 << 9];

#define P 998244353

int main()

{

	scanf("%d",&n);

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

	int ans = 0;

	memset(f,0,sizeof(f));

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

	{

		int v = a[i] & ((1 << 9) - 1);

		int top = a[i] >> 9,bot = (a[i] ^ (top << 9));

		int val = 0;

		for(int j = v;;j = (j - 1) & v)

		{

			val = (val + f[top][j]) % P;

			if(j == 0)break;

		}

		v = ((1 << 9) - 1) ^ top;

		val = (val + 1) % P;

		for(int j = v;;j = (j - 1) & v)

		{

			f[j ^ top][bot] = (f[j ^ top][bot] + val) % P;

			if(j == 0)break;

		}

	}

	for(int i = 0;i < (1 << 9);++i)ans = (ans + f[(1 << 9) - 1][i]) % P;

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

	return 0;

}