結果
問題 | No.803 Very Limited Xor Subset |
ユーザー |
![]() |
提出日時 | 2019-03-17 23:29:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 375 ms / 2,000 ms |
コード長 | 5,195 bytes |
コンパイル時間 | 1,939 ms |
コンパイル使用メモリ | 177,604 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-08 03:27:58 |
合計ジャッジ時間 | 11,477 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h>using namespace std;using lint = long long int;using pint = pair<int, int>;using plint = pair<lint, lint>;struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; returnos; }template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}";return os; }template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; returnos; }template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }template<typename T> void mmax(T &m, const T q) { if (m < q) m = q; }template<typename T> void mmin(T &m, const T q) { if (m > q) m = q; }template<typename T1, typename T2> pair<T1, T2> operator+(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }template<typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;constexpr lint MOD = 1000000007;// Solve ax+by=gcd(a, b)lint extgcd(lint a, lint b, lint &x, lint &y){lint d = a;if (b != 0) d = extgcd(b, a % b, y, x), y -= (a / b) * x;else x = 1, y = 0;return d;}// Calc a^(-1) (MOD m)lint mod_inverse(lint a, lint m){lint x, y;extgcd(a, m, x, y);return (m + x % m) % m;}vector<vector<lint>> gauss_jordan(vector<vector<lint>> mtr, lint mod){// Gauss-Jordan elimination 行基本変形のみを用いるガウス消去法int H = mtr.size(), W = mtr[0].size(), c = 0;REP(h, H){if (c == W) break;int piv = -1;FOR(j, h, H) if (mtr[j][c]){if (piv == -1 or abs(mtr[j][c]) > abs(mtr[piv][c])) piv = j;}if (piv == -1) { c++; h--; continue; }swap(mtr[piv], mtr[h]);if (h != piv) REP(w, W) mtr[piv][w] = mtr[piv][w] ? mod - mtr[piv][w] : 0; // 行列式符号不変lint pivinv = mod_inverse(mtr[h][c], mod);FOR(hh, h + 1, H) IFOR(w, c, W) mtr[hh][w] = (mtr[hh][w] - mtr[h][w] * mtr[hh][c] % mod * pivinv % mod + mod) % mod;c++;}return mtr;}int rank_gauss_jordan(const vector<vector<lint>> &mtr){// gauss_jordanを実行した後の行列のランク計算IREP(h, mtr.size()) for (auto v : mtr[h]) if (v) return h + 1;return 0;}lint power(lint x, lint n, lint MOD){lint ans = 1;while (n>0){if (n & 1) (ans *= x) %= MOD;(x *= x) %= MOD;n >>= 1;}return ans;}constexpr int D = 31;int main(){lint N, M, X;cin >> N >> M >> X;vector<lint> A(N);cin >> A;vector<vector<lint>> mat(D + M, vector<lint>(N + 1));vector<lint> v(D + M);REP(d, D) v[d] = ((X >> d) & 1);REP(i, N) REP(d, D) mat[d][i] = ((A[i] >> d) & 1);REP(j, M){int t, l, r;cin >> t >> l >> r;FOR(k, l - 1, r) mat[D + j][k] = 1;v[D + j] = t;}REP(j, D + M) mat[j][N] = v[j];auto mat2 = gauss_jordan(mat, 2);int h1 = 0, h2 = 0;REP(i, N) REP(j, D + M) if (mat2[j][i]) mmax(h1, j);REP(j, D + M) if (mat2[j][N]) mmax(h2, j);if (h2 > h1){cout << 0 << endl;return 0;}for (auto &vec : mat2) vec.pop_back();int rnk = rank_gauss_jordan(mat2);cout << power(2, N - rnk, MOD) << endl;}