题目描述
给你一个长度为\(n\)的数列\(a\)，求有多少个长度\(\geq 2\)的不上升子序列\(a_{b_1},a_{b_2},\ldots,a_{b_k}\)满足
\[\prod_{i=2}^k\binom{a_{b_{i-1}}}{a_{b_i}}\mod 2>0
\]
\]
答案对\({10}^9+7\)取模。
\(n\leq211985,a_i\leq 233333\)
\(\forall i\neq j,a_i\neq 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\n",ans);
return 0;
}