結果

問題 No.1930 XOR of Two Range
コンテスト
ユーザー SSRS
提出日時 2022-05-06 21:43:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 556 ms / 2,000 ms
コード長 1,132 bytes
コンパイル時間 1,709 ms
コンパイル使用メモリ 175,888 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-07-05 22:54:42
合計ジャッジ時間 3,725 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
long long solve(long long N, int p){
  if (N == -1){
    return 0;
  }
  long long ans = 0;
  vector<vector<int>> dpcnt(2, vector<int>(52, 0));
  vector<vector<long long>> dpxor(2, vector<long long>(52, 0));
  dpcnt[0][51] = 1;
  for (int i = 50; i >= 0; i--){
    for (int j = 0; j < 2; j++){
      for (int k = 0; k < 2; k++){
        bool ok = true;
        if (i == 1 && k != p / 2 % 2){
          ok = false;
        }
        if (j == 0 && (N >> i & 1) == 0 && k == 1){
          ok = false;
        }
        if (ok){
          int j2 = j;
          if ((N >> i & 1) == 1 && k == 0){
            j2 = 1;
          }
          dpcnt[j2][i] += dpcnt[j][i + 1];
          dpcnt[j2][i] %= 2;
          dpxor[j2][i] ^= dpxor[j][i + 1];
          if (dpcnt[j][i + 1] == 1 && k == 1){
            dpxor[j2][i] ^= (long long) 1 << i;
          }
        }
      }
    }
  }
  return dpxor[1][0];
}
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    long long L, R;
    cin >> L >> R;
    cout << (solve(L + R + 1, L * 2 % 4) ^ solve(L * 2 - 1, L * 2 % 4)) << endl;
  }
}
0