题目链接：点击打开链接
题目描述：给出n个数，求从这n个数中任意取出一些数（至少取一个）相互异或之后大于m的方案数？
解题思路：分析由于n<=40&&m<=10^6,因此我们可以枚举所有可能的异或值，时间复杂度40*10^6.
采用动态规划的思想dp[i&1][j]=d[(i-1)&1][j]+d[(i-1)&1][j^a[i]];由于40*10^6太大，所以此处我们采用滚动数组
代码：
#include <cstdio>#include <cstring>using namespace std;const int maxn=1<<20;long long dp[2][maxn+10];int d[41];int n,m;int main(){int T;scanf("%d",&T);for(int t=1;t<=T;++t){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d",&d[i]);memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=1;i<=n;++i){for(int j=0;j<maxn;++j)dp[i&1][j]=dp[(i-1)&1][j]+dp[(i-1)&1][j^d[i]];}long long ans=0;int x=n&1;for(int i=m;i<maxn;i++)ans+=dp[x][i];printf("Case #%d: %I64d\n",t,ans);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
缘是浪漫的相遇，瞬间让你我的心化为永恒！
