预备知识：
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+7; int a[N]; int dp[N][N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; 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=1;i<=n;++i) read(a[i]); dp[0][0]=1; for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) { dp[i][j]=1; for(int k=1;k<j;++k) if(judge(a[k],a[j])) { dp[i][j]+=dp[i-1][k]; dp[i][j]-=dp[i][j]>=mod ? mod : 0; } } int ans=0; for(int i=1;i<=n;++i) { ans+=dp[n][i]-1; ans-=ans>=mod ? mod : 0; } 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+7; int a[N]; int dp[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int main() { int n; read(n); for(int i=1;i<=n;++i) read(a[i]); for(int i=1;i<=n;++i) dp[i]=1; for(int i=1;i<=n;++i) { for(int j=1;j<i;++j) if((a[j]&a[i])==a[i]) dp[i]+=dp[j]; } int ans=0; for(int i=1;i<=n;++i) { ans+=dp[i]-1; ans-=ans>=mod ? mod : 0; } 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+7; int a[N]; int dp[N]; int pos[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int main() { int n; read(n); for(int i=1;i<=n;++i) read(a[i]),pos[a[i]]=i; int bit,sum; for(int i=1;i<=n;++i) { dp[a[i]]++; for(int j=(a[i]-1)&a[i];j;j=(j-1)&a[i]) if(pos[j]>i) { dp[j]+=dp[a[i]]; dp[j]-=dp[j]>=mod ? mod : 0; } } int ans=0; for(int i=1;i<=n;++i) { ans+=dp[a[i]]-1; ans-=ans>=mod ? mod : 0; } printf("%d",ans); }
常数优化：
边读入边计算，接着累计进答案
就可以不用判断子集是否在i的后面
因为在前面的话，前面的已经累积进答案了
#include<cstdio> #include<iostream> using namespace std; #define N 233334 const int mod=1e9+7; int a[N]; int dp[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int main() { int n,x; int ans=0; read(n); for(int i=1;i<=n;++i) { read(x); dp[x]++; for(int j=(x-1)&x;j;j=(j-1)&x) { dp[j]+=dp[x]; dp[j]-=dp[j]>=mod ? mod : 0; } ans+=dp[x]-1; ans-=ans>=mod ? mod : 0; } printf("%d",ans); }