预备知识：
C（n，m）是奇数的充要条件是 n&m==m
由卢卡斯定理可以推出
选出的任意相邻两个数a，b 的组合数计算C（a，b）必须是奇数
所以可以设dp[i][j] 表示前i个数里面，选的最后一个数是第j个数的方案数
转移的时候，枚举前i-1个数选的最后一个数k，
若C（k，i）是奇数,dp[i][j]+=dp[i-1][k]
时间复杂度：O（n^3）
#include<cstdio>
#include<iostream> using namespace std; #define N 20 const int mod=1e9+; int a[N]; int dp[N][N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool judge(int x,int y)
{
if(!x) return true;
return (x&y)==y;
} int main()
{
int n;
read(n);
for(int i=;i<=n;++i) read(a[i]);
dp[][]=;
for(int i=;i<=n;++i)
for(int j=;j<=i;++j)
{
dp[i][j]=;
for(int k=;k<j;++k)
if(judge(a[k],a[j]))
{
dp[i][j]+=dp[i-][k];
dp[i][j]-=dp[i][j]>=mod ? mod : ;
}
}
int ans=;
for(int i=;i<=n;++i)
{
ans+=dp[n][i]-;
ans-=ans>=mod ? mod : ;
}
printf("%d",ans);
}
优化：
dp[i] 表示选的最后一个数是第i个数的方案数
枚举前面的i-1个数，
若C（a[i],a[j]）是奇数，dp[i]+=dp[j]
时间复杂度：O（n^2）
#include<cstdio>
#include<iostream> using namespace std; #define N 2018 const int mod=1e9+; int a[N]; int dp[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
int n;
read(n);
for(int i=;i<=n;++i) read(a[i]);
for(int i=;i<=n;++i) dp[i]=;
for(int i=;i<=n;++i)
{
for(int j=;j<i;++j)
if((a[j]&a[i])==a[i]) dp[i]+=dp[j];
}
int ans=;
for(int i=;i<=n;++i)
{
ans+=dp[i]-;
ans-=ans>=mod ? mod : ;
}
printf("%d",ans);
}
再优化：
dp[i] 表示选的最后一个数是i的方案数
dp[i] 能转移到i的子集，
所以枚举子集j，若j在i的后面，那么dp[j]+=dp[i]
时间复杂度：O（3^（logn））
#include<cstdio>
#include<iostream> using namespace std; #define N 233334 const int mod=1e9+; int a[N]; int dp[N];
int pos[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
int n;
read(n);
for(int i=;i<=n;++i) read(a[i]),pos[a[i]]=i;
int bit,sum;
for(int i=;i<=n;++i)
{
dp[a[i]]++;
for(int j=(a[i]-)&a[i];j;j=(j-)&a[i])
if(pos[j]>i)
{
dp[j]+=dp[a[i]];
dp[j]-=dp[j]>=mod ? mod : ;
}
}
int ans=;
for(int i=;i<=n;++i)
{
ans+=dp[a[i]]-;
ans-=ans>=mod ? mod : ;
}
printf("%d",ans);
}
常数优化：
边读入边计算，接着累计进答案
就可以不用判断子集是否在i的后面
因为在前面的话，前面的已经累积进答案了
#include<cstdio>
#include<iostream> using namespace std; #define N 233334 const int mod=1e9+; int a[N]; int dp[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
int n,x;
int ans=;
read(n);
for(int i=;i<=n;++i)
{
read(x);
dp[x]++;
for(int j=(x-)&x;j;j=(j-)&x)
{
dp[j]+=dp[x];
dp[j]-=dp[j]>=mod ? mod : ;
}
ans+=dp[x]-;
ans-=ans>=mod ? mod : ;
}
printf("%d",ans);
}