結果
問題 |
No.1142 XOR と XOR
|
ユーザー |
|
提出日時 | 2020-08-01 09:38:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,000 ms |
コード長 | 1,146 bytes |
コンパイル時間 | 1,811 ms |
コンパイル使用メモリ | 171,280 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-11-08 03:39:37 |
合計ジャッジ時間 | 4,428 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1e9 + 7; int main() { ll n, m, k; cin >> n >> m >> k; vector<int> a(n), b(m); for (auto &i : a) cin >> i; for (auto &i : b) cin >> i; vector<int> suma(n + 1), sumb(m + 1); for (int i = 0; i < n; i++) suma[i + 1] ^= suma[i] ^ a[i]; for (int i = 0; i < m; i++) sumb[i + 1] ^= sumb[i] ^ b[i]; vector<ll> cnta(1024), cntb(1024); for (int i = 0; i < n + 1; i++) cnta[suma[i]]++; for (int i = 0; i < m + 1; i++) cntb[sumb[i]]++; vector<ll> ncnta(1024), ncntb(1024); for (int i = 0; i < 1024; i++) for (int j = i; j < 1024; j++) { if (i == j) { ncnta[i ^ j] += (cnta[i]-1) * cnta[j]/2 % MOD; ncnta[i ^ j] %= MOD; ncntb[i ^ j] += (cntb[i]-1) * cntb[j]/2 % MOD; ncntb[i ^ j] %= MOD; continue; } ncnta[i ^ j] += cnta[i] * cnta[j] % MOD; ncnta[i ^ j] %= MOD; ncntb[i ^ j] += cntb[i] * cntb[j] % MOD; ncntb[i ^ j] %= MOD; } ll ans = 0; for(int i = 0;i<1024;i++) { for(int j = 0;j<1024;j++) { if((i^j)==k) { ans += ncnta[i]*ncntb[j]; ans %= MOD; } } } cout << ans << endl; }