O - Happy Matt Friends

本文主要是介绍O - Happy Matt Friends，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

（1）条件及问题：给定N个数，找到异或值大于等于M的总方案数；

（2）分析：

1. 可以dfs（）枚举，超时；
2. 考虑dp,dp[i][j]描述在前i个数中选，值为j的方案数；
3. 则dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^a[i]];

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
#define maxx 1024*1024
int a[45];
ll dp[45][maxx];///dp[i][j]代表从第1个数到第i个数，亦或后结果为j的方案的数目
///任何数和0异或后的·结果依然是本身
int main()
{int t,n,m,c=1;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)scanf("%d",&a[i]);dp[0][0]=1;for(int i=1; i<=n; i++)for(int j=0; j<maxx; j++)dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]];ll sum=0;for(int k=m; k<maxx; k++)sum+=dp[n][k];printf("Case #%d: %lld\n",c++,sum);}
}

这篇关于O - Happy Matt Friends的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---