Submission #2081874


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(n) ((int)1e##n)
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
int reader(string& c) { int i; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c.push_back(i); for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c.push_back(i); }; return sz(c); }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const string& x, char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
template<class T> void writerArr(vector<T>& x) { writerArr(x.data(), (int)x.size()); }

template<class T> void chmin(T& a, const T& b) { if (a > b) a = b; }
template<class T> void chmax(T& a, const T& b) { if (a < b) a = b; }

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
ll mod_pow(ll a, ll n, ll mod) {
	ll ret = 1;
	ll p = a % mod;
	while (n) {
		if (n & 1) ret = ret * p % mod;
		p = p * p % mod;
		n >>= 1;
	}
	return ret;
}
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
ll mod_inv(ll a, ll m) { ll x, y; extgcd<ll>(a, m, x, y); return (m + x % m) % m; }

const int NCK = 1600;
const int MOD = ten(9) + 7;

ll nck[NCK + 1][NCK + 1];
void calc_nck() {
	FOR(i, NCK) {
		nck[i][0] = nck[i][i] = 1;
		for (int j = 1; j <= i; j++) {
			nck[i + 1][j] = (nck[i][j - 1] + nck[i][j]) % MOD;
		}
	}
}

int a[1024][1024];

int main() {
	calc_nck();

	int n, k, X, y; reader(n, k, X, y);
	vector<int> x(n);
	FOR(i, n) reader(x[i]);
	FOR(i, k) FOR(j, k) {
		reader(a[i][j]);
		a[i][j] ^= X;
	}
	y ^= X;
	bool ok = true;
	FOR(i, k) FOR(j, k) {
		if (i == j) {
			if (a[i][j] == 0 || a[i][j] == y) {
			} else {
				ok = false;
			}
			continue;
		}

		int val = a[0][i] ^ a[0][j];
		if (val == a[i][j] || val == (a[i][j] ^ y)) {
		} else {
			ok = false;
		}
	}
	if (!ok) {
		puts("0");
		return 0;
	}
	map<int, Pii> ori;
	FOR(i, n) {
		int a = x[i];
		int b = a ^ y;
		int use = min(a, b);
		if (a < b) {
			ori[use].first++;
		} else {
			ori[use].second++;
		}
	}

	map<int, int> mp;
	FOR(i, k) {
		if (i == 0) {
			continue;
		}
		int c = a[0][i];
		int b = c ^ y;
		int use = min(c, b);
		mp[use]++;
	}

	ll aans = 0;
	set<int> used;
	FOR(i, n) {
		int base = x[i];
		if (used.count(base)) continue;
		used.insert(base);

		{
			int a = x[i];
			int b = a ^ y;
			int use = min(a, b);
			if (a < b) {
				ori[use].first--;
			} else {
				ori[use].second--;
			}
		}

		ll ans = 1;
		for (auto& kv : mp) {
			int a = kv.first ^ base;
			int b = a ^ y;
			int use = min(a, b);

			ll tmp = 0;
			Pii u = ori[use];
			int p = kv.second;
			FOR(l, p + 1) {
				int r = p - l;
				if (l <= u.first && r <= u.second) {
					tmp += nck[p][r];
				}
			}
			tmp %= MOD;
			ans = ans * tmp % MOD;
		}
		aans = (aans + ans) % MOD;

		{
			int a = x[i];
			int b = a ^ y;
			int use = min(a, b);
			if (a < b) {
				ori[use].first++;
			} else {
				ori[use].second++;
			}
		}
	}
	writerLn(aans);

	return 0;
}

Submission Info

Submission Time
Task D - XOR XorY
User math
Language C++14 (GCC 5.4.1)
Score 800
Code Size 5614 Byte
Status
Exec Time 98 ms
Memory 24576 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 800 / 800 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt
Case Name Status Exec Time Memory
00_example_01.txt 8 ms 20352 KB
00_example_02.txt 8 ms 20352 KB
00_example_03.txt 8 ms 20352 KB
01.txt 8 ms 20352 KB
02.txt 8 ms 20352 KB
03.txt 8 ms 20352 KB
04.txt 8 ms 20352 KB
05.txt 8 ms 20352 KB
06.txt 8 ms 20480 KB
07.txt 8 ms 20480 KB
08.txt 8 ms 20352 KB
09.txt 8 ms 20480 KB
10.txt 8 ms 20352 KB
11.txt 56 ms 22272 KB
12.txt 98 ms 24576 KB
13.txt 35 ms 21376 KB
14.txt 42 ms 21632 KB
15.txt 39 ms 21504 KB
16.txt 46 ms 21760 KB
17.txt 71 ms 24576 KB
18.txt 85 ms 24576 KB
19.txt 63 ms 24576 KB
20.txt 67 ms 24576 KB
21.txt 38 ms 24448 KB
22.txt 36 ms 24448 KB
23.txt 31 ms 24448 KB
24.txt 31 ms 24448 KB
25.txt 33 ms 24448 KB
26.txt 12 ms 22016 KB
27.txt 10 ms 21632 KB
28.txt 9 ms 20992 KB
29.txt 9 ms 21120 KB
30.txt 11 ms 22016 KB
31.txt 10 ms 21632 KB
32.txt 9 ms 20992 KB
33.txt 9 ms 21120 KB
34.txt 23 ms 24320 KB
35.txt 27 ms 24320 KB