Submission #4074840

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

ll dp[2][101010];

int main(){
	ll N, K;
	cin >> N >> K;
	vector<ll> a(N);
	REP(i, N) cin >> a[i];

	sort(a.begin(), a.end());
	REP(i, 2)REP(j, 101010) dp[i][j] = 0;
	dp[0][0] = 1;
	ll h = 0;
	REP(i, N){
		REP(j, (h|a[i])+1){
			dp[(i+1)%2][j] = 0;
		}
		REP(j, h+1){
			dp[(i+1)%2][j] += dp[i%2][j];
			dp[(i+1)%2][j] %= mod;
			dp[(i+1)%2][j^a[i]] += dp[i%2][j];
			dp[(i+1)%2][j^a[i]] %= mod;
		}
		h |= a[i];
	}
	cout << dp[N%2][K] << endl;
    return 0;
}

Submission Info

Judge Result