这题目是14年北京赛区的原题。讲题的时候说有三种解法，我们是用dp做的当时。原题目链接：Happy Matt Friends
题意就不在说了。由于要求的是满足条件的种数。
我们定义状态dp【i】【j】：当我们把第 i 个数放进去之后得到 j 的种数是多少
那么我们能够得到状态转移方程：dp【i】【j^ a [ i ] 】 += dp【i-1】【j】
就是当前得到每一个 j ^ a [ i ] 有前 i-1 个数得到。整个dp一遍就是得到结果了。
还有注意这里数组比較大。直接开的话会超内存，所以要用滚动数组优化。
AC代码：
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
const int N = 1100100;
LL dp[3][N];
int a[50];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(dp,0,sizeof(dp));
int ma = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>ma)
ma = a[i];
}
dp[0][0] = 1;
for(int i=1;i<=n;i++)
{
memset(dp[i%2],0,sizeof(dp[i%2]));
for(int j=0;j<=ma;j++)
{
dp[i%2][j^a[i]] += dp[(i+1)%2][j];
dp[i%2][j] += dp[(i+1)%2][j];
if((j^a[i])>ma)
ma = (j^a[i]);
}
}
LL ans = 0;
for(int i=m;i<=ma;i++)
ans+=dp[n%2][i];
printf("%lld
",ans);
}
return 0;
}