题目描述
给你一个长度为(n)的数列(a)，求有多少个长度(geq 2)的不上升子序列(a_{b_1},a_{b_2},ldots,a_{b_k})满足
[prod_{i=2}^kinom{a_{b_{i-1}}}{a_{b_i}}mod 2>0
]
答案对({10}^9+7)取模。
(nleq211985,a_ileq 233333)
(forall i eq j,a_i eq a_j)
题解
水题。
先忽略长度(geq 2)这个条件。
根据卢卡斯定理，有(a_{b_i}|a_{b_{i-1}})。
从前往后DP。
设(f_i)为前面那部分，最后一个数是(i)的方案数。
转移直接枚举(a_i|j)，让(f_{a_i}+=f_j)。
时间复杂度：枚举子集的复杂度，(O(3^{log max_{i=1}^na_i}))
p.s. gift在德语中的意思是毒。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int p=1000000007;
int f[1000010];
int main()
{
int n;
scanf("%d",&n);
int i,x,j;
int ans=0;
for(i=1;i<=n;i++)
{
scanf("%d",&x);
f[x]=1;
for(j=(x+1)|x;j<=233333;j=(j+1)|x)
f[x]=(f[x]+f[j])%p;
ans=(ans+f[x])%p;
}
ans=(ans-n+p)%p;
printf("%d
",ans);
return 0;
}