fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl     '\n'
  5. #define int      long long
  6.  
  7. const int N = 2e5, oo = 2e18, MOD = 998244353;
  8.  
  9. int xorfromZeroToN(int n) {
  10.     if (n % 4 == 0) return n;
  11.     return n ^ xorfromZeroToN(n-1);
  12. }
  13.  
  14. int xRange(int l, int r) {
  15.     if (l == 0)
  16.         return xorfromZeroToN(r);
  17.     return xorfromZeroToN(r) ^ xorfromZeroToN(l-1);
  18. }
  19.  
  20. int cnt(int n) {
  21.     if (n < 0)
  22.         return 0;
  23.     if (n == 0)
  24.         return 1; 
  25.     int ans = (n >= 3) + 1;
  26.     if (n >= 3)
  27.         ans += ((n - 3) / 4);
  28.     return ans;
  29. }
  30. int cnt2(int n) {
  31.     if (n <= 0)
  32.         return 0;
  33.     int ans = 1;
  34.     if (n >= 1)
  35.         ans += (n - 1) / 4;
  36.     return ans;
  37. }
  38.  
  39. int ans(int l, int r) {
  40.     if (l > r)
  41.         return 0;
  42.     int c = cnt(r) - cnt(l-1);
  43.     int c2 = cnt2(r) - cnt2(l-1);
  44.     // cout << c  << ' ' << c2 << endl;
  45.     return c * (c - 1) / 2 + c2 * (c2 - 1) / 2;
  46. }
  47. // 0 1 2 0
  48.  
  49. void solve() {
  50.     int n, x; cin >> n >> x;
  51.     // cout << cnt(5) << ' ' << cnt2(5) << endl;
  52.     // cout << cnt(0) << ' ' << cnt2(0) << endl;
  53.     // cout << cnt(4) << ' ' << cnt2(4) << endl;
  54.     // 0 1 3 0 4 1
  55.     // cout << cnt(7) << ' ' << cnt2(7) << endl;
  56.     // cout << cnt(0) << ' ' << cnt2(0) << endl;
  57.     // cout << ans(1, x - 1) << endl;
  58.     // cout << ans(x + 1, n) << endl;
  59.     int res = ans(0, n) % MOD;
  60.     // cout << ans(0, n) << ' ' << ans(2, n) << ' ' << ans(0, 0) << endl;
  61.     res = (res - ans(x, n) % MOD + MOD) % MOD;
  62.     res = ((res - ans(0, x - 1) % MOD) + MOD) % MOD;
  63.     cout << res << endl;
  64.     // int ans = 0;
  65.     // for (int l = 1; l <= x; l++) {
  66.     //     for (int r = x; r <= n; r++) {
  67.     //         if (xRange(l, r) == 0) {
  68.     //             cout << l << ' ' << r << endl;
  69.     //         }
  70.     //     }
  71.     // }
  72.     // for (int i = 0; i <= 8; i++) {
  73.     //     cout << i << ' ' << xorfromZeroToN(i) << endl;
  74.     // }
  75. }
  76.  
  77.  
  78. signed main() {
  79.     ios_base::sync_with_stdio(false); 
  80.     cin.tie(NULL); cout.tie(NULL);
  81.     // #ifndef ONLINE_JUDGE 
  82.     //    freopen("input.txt", "r", stdin); 
  83.     //    freopen("output.txt", "w", stdout); 
  84.     // #endif 
  85.     int t; t = 1;
  86.     cin >> t;
  87.     while (t--) solve();
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/8hTd5v
language:
C++ (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!