题目描述
给出一个长度为 $n$ 的序列，求所有长度大于等于2的子序列个数，满足：对于子序列中任意两个相邻的数 $a$ 和 $b$ （$a$ 在 $b$ 前面），${achoose b}mod 2 eq 0$。答案对 $10^9+7$取模。
输入
第一行一个整数 $n$ 。
接下来 $n$ 行，每行一个整数，这 $n$ 行中的第 $i$ 行，表示 $a_i$ 。
$1le nle 211985,1le a_ile 233333$
输出
一行一个整数表示答案。
样例输入
4
15
7
3
1
样例输出
11
题解
数论+状压dp
考虑Lucas定理求组合数的过程： ${nchoose m}mod 2={{nmod 2}choose{mmod 2}}·{{n/2}choose{m/2}}mod 2$
相当于 ${nmod 2}choose{mmod 2}$ 是 $n$ 和 $m$ 的二进制最后一位，如果结果不等于0，则每一次递归的 ${nmod 2}choose{mmod 2}$ 都不能等于0。
考虑实际意义，即不能存在二进制某一位，$n$ 的该位为0， $m$ 的该位为1。那么就相当于 $m$ 是 $n$ 的子集。
设 $f[i]$ 表示以数 $i$ 结尾的满足条件的子序列的数目，那么对于数 $j$ ，如果 ${ichoose j}mod 2 eq 0$（即满足上面的子集性质），且 $j$ 出现的位置在 $i$ 后面 ，那么就可以从 $j$ 更新到 $i$ ，$f[i]+=f[j]+1$。
可以通过枚举子集的技巧 $j=i and (j-1)$，使得时间复杂度为 $O(3^{log_2233333})=O(322137234)=O(能过)$
#include <cstdio>
#define mod 1000000007
int p[233334] , f[233334];
int main()
{
int n , i , j , x , ans = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , p[x] = i;
for(i = 1 ; i <= 233333 ; i ++ )
if(p[i])
for(j = i & (i - 1) ; j ; j = i & (j - 1))
if(p[j] > p[i])
f[i] = (f[i] + f[j] + 1) % mod;
for(i = 1 ; i <= 233333 ; i ++ ) ans = (ans + f[i]) % mod;
printf("%d
" , ans);
return 0;
}