Submission #396025

#	Time	Username	Problem	Language	Result	Execution time	Memory
396025		rama_pang	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	1654 ms	13380 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;

template<int MOD>
class ModInt {
 public:
  int v;

  ModInt() : v(0) {}
  ModInt(long long _v) {
    v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
    if (v < 0) v += MOD; }

  friend bool operator==(const ModInt &a, const ModInt &b) { return a.v == b.v; }
  friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v != b.v; }
  friend bool operator<(const ModInt &a, const ModInt &b) { return a.v < b.v; }
  friend bool operator<=(const ModInt &a, const ModInt &b) { return a.v <= b.v; }
  friend bool operator>(const ModInt &a, const ModInt &b) { return a.v > b.v; }
  friend bool operator>=(const ModInt &a, const ModInt &b) { return a.v >= b.v; }

  ModInt& operator+=(const ModInt &a) {
    if ((v += a.v) >= MOD) v -= MOD;
    return *this; }
  ModInt& operator-=(const ModInt &a) {
    if ((v -= a.v) < 0) v += MOD;
    return *this; }
  ModInt& operator*=(const ModInt &a) {
    v = 1ll * v * a.v % MOD;
    return *this; }
  ModInt& operator/=(const ModInt &a) {
    return (*this) *= inverse(a); }

  friend ModInt pow(ModInt a, long long x) {
    ModInt res = 1; assert(x >= 0);
    for (; x; x /= 2, a *= a) if (x & 1) res *= a;
    return res; }
  friend ModInt inverse(ModInt a) {
    assert(a.v != 0);
    return pow(a, MOD - 2); }

  ModInt operator+() const { return ModInt(v); }
  ModInt operator-() const { return ModInt(-v); }
  ModInt operator++() const { return *this += 1; }
  ModInt operator--() const { return *this -= 1; }

  friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
  friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
  friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
  friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }

  friend istream& operator>>(istream &is, ModInt &v) { is >> v.v; return is; }
  friend ostream& operator<<(ostream &os, const ModInt &v) { os << v.v; return os; }
};

const int MOD = 1e9 + 7;
using Mint = ModInt<MOD>;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  const int M = 128;

  int N;
  cin >> N;

  vector<int> A(N + 1);
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
  }

  int Q;
  cin >> Q;

  vector<int> L(Q), R(Q), K(Q);
  for (int i = 0; i < Q; i++) {
    cin >> L[i] >> R[i] >> K[i];
  }

  Mint answer = 0;
  for (int a = 0; a < 7; a++) { // a-th bit of left endpoint
    for (int b = 0; b < 7; b++) { // b-th bit of right endpoint
      static vector<vector<int>> dpR(N + 2, vector<int>(N + 2));
      static vector<vector<int>> dpL(N + 2, vector<int>(N + 2));
      static vector<vector<int>> dpB(N + 2, vector<int>(N + 2));

      for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= N + 1; j++) {
          dpR[i][j] = dpL[i][j] = dpB[i][j] = 0;
        }
      }

      const auto AddRect = [&](vector<vector<int>> &s, int a, int b, int c, int d) { // (a, b) to (c, d)
        s[a][b] += 1;
        s[a][d + 1] -= 1;
        s[c + 1][b] -= 1;
        s[c + 1][d + 1] += 1;
      };

      for (int i = 0; i < Q; i++) {
        bool inA = (K[i] >> a) & 1;
        bool inB = (K[i] >> b) & 1;
        if (inA && inB) {
          // Affect only right: [1, L[i]-1] * [L[i], R[i]]
          AddRect(dpR, 1, L[i], L[i] - 1, R[i]);
          // Affect only left : [L[i], R[i]] * [R[i] + 1, N]
          AddRect(dpL, L[i], R[i] + 1, R[i], N);
          // Affect both      : [L[i], R[i]] * [L[i], R[i]]
          AddRect(dpB, L[i], L[i], R[i], R[i]);
        } else if (inA) {
          // Affect only left : [L[i], R[i]] * [L[i], N]
          AddRect(dpL, L[i], 1, R[i], N);
        } else if (inB) {
          // Affect only right: [1, R[i]] * [L[i], R[i]]
          AddRect(dpR, 1, L[i], N, R[i]);
        }
      }

      for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
          dpL[i][j] += dpL[i - 1][j] + dpL[i][j - 1] - dpL[i - 1][j - 1];
          dpR[i][j] += dpR[i - 1][j] + dpR[i][j - 1] - dpR[i - 1][j - 1];
          dpB[i][j] += dpB[i - 1][j] + dpB[i][j - 1] - dpB[i - 1][j - 1];
        }
      }

      const auto Get = [&](int x, int parity) -> int {
        return x == 0 ? (parity == 0) : ((MOD + 1) / 2);
      };

      for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
          int initL = (A[i] >> a) & 1;
          int initR = (A[j] >> b) & 1;
          Mint mul = Mint(1 + (i != j)) * i * (N - j + 1) * (1 << a) * (1 << b);
          for (int tl = 0; tl < 2; tl++) { // toggle left even/odd times
            for (int tr = 0; tr < 2; tr++) { // toggle right even/odd times
              for (int tb = 0; tb < 2; tb++) { // toggle both even/odd times
                if ((initL ^ tl ^ tb) == 1 && (initR ^ tr ^ tb) == 1) { // both bits are on
                  answer += mul * Get(dpL[i][j], tl) * Get(dpR[i][j], tr) * Get(dpB[i][j], tb);
                }
              }
            }
          }
        }
      }
    }
  }

  for (int i = 1; i <= Q; i++) answer *= 2;

  cout << answer << '\n';
  return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:62:13: warning: unused variable 'M' [-Wunused-variable]
   62 |   const int M = 128;
      |             ^

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8