結果
問題 |
No.1142 XOR と XOR
|
ユーザー |
![]() |
提出日時 | 2020-07-31 23:55:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 197 ms / 2,000 ms |
コード長 | 2,256 bytes |
コンパイル時間 | 2,247 ms |
コンパイル使用メモリ | 198,640 KB |
最終ジャッジ日時 | 2025-01-12 11:57:54 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> #define _overload3(_1, _2, _3, name, ...) name #define _rep(i, n) repi(i, 0, n) #define repi(i, a, b) for (int i = (a); i < (b); ++i) #define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__) #define ALL(x) x.begin(), x.end() #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) using namespace std; random_device rnd; mt19937 mt(rnd()); using ll = long long; using lld = long double; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; using PII = pair<int, int>; const int IINF = 1 << 30; const ll INF = 1ll << 60; const ll MOD = 1000000007; ll mpow(ll base, ll num) { if (num <= 0) return 1; ll prev = mpow(base, num / 2); if (num % 2 == 0) { return (prev * prev) % MOD; } else { return (((prev * prev) % MOD) * base) % MOD; } } ll inv(ll num) { return mpow(num, MOD - 2); } int main() { int n, m, k; cin >> n >> m >> k; VI a(n), b(m); rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; VL anum(1024, 0); VL bnum(1024, 0); VL tmp(1024, 0); int cur = 0; int asum = 0; int bsum = 0; rep(i, n) { cur ^= a[i]; tmp[cur]++; } asum = cur; cur = 0; rep(i, 1024) { rep(j, 1024) { if (i == j) anum[i ^ j] += (tmp[i] * (tmp[j] - 1)); else anum[i ^ j] += tmp[i] * tmp[j]; } } rep(i, 1024) { anum[i] /= 2; } rep(i, 1024) { anum[i] += tmp[i]; anum[i] %= MOD; } rep(i, 1024) tmp[i] = 0; cur = 0; rep(i, m) { cur ^= b[i]; tmp[cur]++; } bsum = cur; cur = 0; rep(i, 1024) { rep(j, 1024) { if (i == j) bnum[i ^ j] += (tmp[i] * (tmp[j] - 1)); else bnum[i ^ j] += tmp[i] * tmp[j]; } } rep(i, 1024) { bnum[i] /= 2; } rep(i, 1024) { bnum[i] += tmp[i]; bnum[i] %= MOD; } ll ans = 0; rep(i, 1024) { ans += anum[i] * bnum[k ^ i]; ans %= MOD; } cout << ans << endl; return 0; }