結果
問題 |
No.1142 XOR と XOR
|
ユーザー |
|
提出日時 | 2021-01-30 14:50:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 1,486 bytes |
コンパイル時間 | 2,260 ms |
コンパイル使用メモリ | 195,064 KB |
最終ジャッジ日時 | 2025-01-18 09:54:17 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
typedef long long ll; typedef long double ld; #include <bits/stdc++.h> using namespace std; const ll MOD = 1e9+7; int main() { // aで0~1023が何通りか調べる // bで0~1023が何通りか調べる // xとK xor xの掛け算 // 累積xorで0~1023の各数を求める // n*2で各ペアの数を求める ll n,m,k; std::cin >> n>>m>>k; vector<ll> a(n),b(m); vector<ll> ac(1024),bc(1024); vector<ll> az(1024),bz(1024); ll now = 0; ac[0]++; for (int i = 0; i < n; i++) { std::cin >> a[i]; now = now ^ a[i]; ac[now]++; } now = 0; bc[0]++; for (int i = 0; i < m; i++) { std::cin >> b[i]; now = now ^ b[i]; bc[now]++; } for (int i = 0; i < 1024; i++) { for (int j = i; j < 1024; j++) { if(i==j){ az[i ^ j] += (ac[i] * ac[j] - ac[j])/2; bz[i ^ j] += (bc[i] * bc[j] - bc[j])/2; }else{ az[i ^ j] += ac[i] * ac[j]; bz[i ^ j] += bc[i] * bc[j]; } az[i ^ j] %= MOD; bz[i ^ j] %= MOD; } } // // 1,2,0 // for (int i = 0; i < 1024; i++) { // std::cout << az[i]<<" "<<b[i] << std::endl; // } ll ans = 0; for (int i = 0; i < 1024; i++) { ans += az[i]*bz[k^i]%MOD; ans %= MOD; } std::cout << ans << std::endl; }