# 题目

## Description

Matt has N friends. They are playing a game together.

Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins.

Matt wants to know the number of ways to win.

## Input

The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 10 6).

In the second line, there are N integers ki (0 ≤ k i ≤ 10 6), indicating the i-th friend’s magic number.

## Output

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y indicates the number of ways where Matt can win.

2
3 2
1 2 3
3 3
1 2 3

Case #1: 4
Case #2: 2

## Hint

In the rst sample, Matt can win by selecting:
friend with number 1 and friend with number 2. The xor sum is 3.
friend with number 1 and friend with number 3. The xor sum is 2.
friend with number 2. The xor sum is 2.
friend with number 3. The xor sum is 3.

# 题解

`dp[i][j]` 表示前 `i` 个人中选取任一个异或和为 `j` 的选法个数

• 如果不选择第 `i` 个人,则有 `dp[i][j] = dp[i-1][j]`
• 如果选择第 `i` 个人,则有 `dp[i][j^a[i]] = dp[i-1][j]`

# 代码

```/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <bitset>
using namespace std;

const int maxn = 45;
const int maxm = 1000005;

int a[maxn];
int dp[maxn][maxm];

void Do() {
int n,m;
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));

for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
}
dp = 1;

for(int i = 1;i <= n;i++) {
for(int j = 0;j < maxm;j++) {
dp[i][j] += dp[i - 1][j];
dp[i][j ^ a[i]] += dp[i - 1][j];
}
}

long long ans = 0;
for(int i = m;i <= maxm;i++)
ans += dp[n][i];

printf("%lld\n",ans);
}

int main(){
int T;
scanf("%d",&T);
for(int i = 1;i <= T;i++) {
printf("Case #%d: ",i);
Do();
}
return 0;
}
```