結果

問題 No.803 Very Limited Xor Subset
コンテスト
ユーザー south37
提出日時 2019-09-16 21:21:43
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 4,119 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 930 ms
コンパイル使用メモリ 107,652 KB
実行使用メモリ 7,040 KB
最終ジャッジ日時 2024-07-07 02:32:09
合計ジャッジ時間 2,126 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<int, int, int> triple;
typedef double D;

int gcd(int a, int b) {
  if (a < b) { swap(a, b); }
  if (b == 0) { return a; }
  return gcd(b, a % b);
}

bool prime(int n) {
  for (int i = 2; i <= sqrt(n); ++i) {
    if (n % i == 0) { return false; }
  }
  return n != 1;
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

ll powmod(ll x, ll n) { // like pow(x, n)
  ll r = 1;
  while (n) {
    if (n & 1) {
      r = r * x % MOD;
    }
    x = x * x % MOD;
    n >>= 1;
  }
  return r;
}

const int COM_MAX = 500010;
ll fac[COM_MAX], facinv[COM_MAX], inv[COM_MAX];
void COMinit() {
  fac[0] = fac[1] = 1;
  facinv[0] = facinv[1] = 1;
  inv[1] = 1;
  for(int i = 2; i < COM_MAX; ++i) {
    fac[i] = fac[i-1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    facinv[i] = facinv[i-1] * inv[i] % MOD;
  }
}

ll COM(ll n, ll k) {
  return (fac[n] * facinv[k] % MOD) * facinv[n-k] % MOD;
}

ll PERM(ll n, ll k) {
  return (fac[n] * facinv[k] % MOD);
}

const int MAX_ROW = 3010; // To be set appropriately.
const int MAX_COL = 3010; // To be set appropriately.

class BitMatrix {
public:
  BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
  inline bitset<MAX_COL>& operator [] (int i) { return val[i]; }

  int H, W;

private:
  bitset<MAX_COL> val[MAX_ROW];
};

ostream& operator << (ostream& s, BitMatrix A) {
  s << endl;
  rep(i, A.H) {
    rep(j, A.W) {
      s << A[i][j] << ", ";
    }
    s << endl;
  }
  return s;
}

int GaussJordan(BitMatrix &A, bool is_extended = false) {
  int rank = 0;
  rep(col, A.W) {
    if (is_extended && col == A.W - 1) { break; }
    int pivot = -1;
    for (int row = rank; row < A.H; ++row) {
      if (A[row][col]) {
        pivot = row;
        break;
      }
    }
    if (pivot == -1) continue;
    swap(A[pivot], A[rank]);
    rep(row, A.H) {
      if (row != rank && A[row][col]) {
        A[row] ^= A[rank];
      }
    }
    ++rank;
  }
  return rank;
}

int linear_equation(BitMatrix A, vector<int> b, vector<int> &res) {
  int m = A.H, n = A.W;
  BitMatrix M(m, n + 1);
  rep(i, m) {
    rep(j, n) {
      M[i][j] = A[i][j];
    }
    M[i][n] = b[i];
  }
  int rank = GaussJordan(M, true);

  // check if it has no solution
  for (int row = rank; row < m; ++row) {
    if (M[row][n]) { return -1; }
  }

  // answer
  res.assign(n, 0);
  rep(i, rank) {
    res[i] = M[i][n];
  }
  return rank;
}

const int DIGIT = 35; // 10^9 ~ 2^30

int main(int argc, char** argv) {
  int N, M, X;
  cin >> N >> M >> X;
  vector<ll> a(N);
  rep(i, N) {
    cin >> a[i];
  }
  vector<triple> tlr;
  rep(i, M) {
    int type, l, r;
    cin >> type >> l >> r;
    --l; --r;
    tlr.push_back(triple(type, l, r));
  }

  BitMatrix A(DIGIT + M, N);  // extend matrix with M conditions.
  // COUT(A);
  vector<int> b(DIGIT + M);
  // Set DIGIT rows.
  rep(d, DIGIT) {
    rep(i, N) {
      if (a[i] & (1LL << d)) {
        A[d][i] = 1;
      }
    }
    if (X & (1LL << d)) {
      b[d] = 1;
    }
  }
  // Set M rows.
  rep(row, M) {
    triple t = tlr[row];
    int type = get<0>(t);
    int l = get<1>(t);
    int r = get<2>(t);
    rep(i, N) {
      if (l <= i && i <= r) {
        A[DIGIT + row][i] = 1;
      }
    }
    b[DIGIT + row] = type;
  }
  // COUT(A);

  vector<int> res;
  int rank = linear_equation(A, b, res);
  // COUT(rank);
  if (rank == -1) {
    cout << 0 << endl;
  } else {
    cout << powmod(2LL, N - rank) << endl;
  }
}
0