位运算相关的状压DP,放一道上来
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; int a[25],b[25]; void solve(int x) { for(int i=1;i<x;i++) { int s1=0,s2=2047; for(int j=1;j<=i;j++)s1^=b[j]; for(int j=i+1;j<=x;j++)s2&=b[j]; if(s1==s2) { ans++; } } } void dfs(int K,int x) { if(x==n+1) { solve(K-1); return; } b[K]=a[x]; dfs(K+1,x+1); dfs(K,x+1); } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); dfs(1,1); printf("%d\n",ans); return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[1005],b[1005]; ll ans,f[1005][2048],g[1005][2048],sum[2048]; int main() { //freopen("sequence.in","r",stdin); //freopen("sequence.out","w",stdout); n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)b[i]=a[n-i+1]; memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { for(int j=0;j<2048;j++) f[i][j]=sum[j^a[i]]; f[i][a[i]]++; for(int j=0;j<2048;j++)sum[j]+=f[i][j]; } memset(sum,0,sizeof(sum)); for(int i=0;i<n;i++) { for(int j=0;j<2048;j++) g[i+1][j&b[i+1]]+=sum[j]; g[i+1][b[i+1]]++; for(int j=0;j<2048;j++)sum[j]+=g[i+1][j]; } memset(sum,0,sizeof(sum)); for(int i=1;i<n;i++) { for(int j=0;j<2048;j++) sum[j]+=f[i][j]; for(int j=0;j<2048;j++) ans+=sum[j]*g[n-i][j]; } printf("%I64d",ans); return 0; }