結果
| 問題 | No.803 Very Limited Xor Subset |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2019-04-23 19:20:36 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 31 ms / 2,000 ms |
| コード長 | 18,608 bytes |
| コンパイル時間 | 2,552 ms |
| コンパイル使用メモリ | 204,620 KB |
| 最終ジャッジ日時 | 2025-01-07 02:54:06 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 43 |
ソースコード
#include <bits/stdc++.h>#pragma GCC diagnostic ignored "-Wsign-compare"#pragma GCC diagnostic ignored "-Wsign-conversion"#define NDEBUG#define SHOW(...) static_cast<void>(0)//!===========================================================!////! dP dP dP !////! 88 88 88 !////! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !////! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !////! 88 88 88. ... 88. .88 88. .88 88. ... 88 !////! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !////!===========================================================!//using ld = long double;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr unsigned int MOD = 1000000007;template <typename T>constexpr T INF = std::numeric_limits<T>::max() / 4;template <typename F>constexpr F PI = static_cast<F>(3.1415926535897932385);std::mt19937 mt{std::random_device{}()};template <typename T>bool chmin(T& a, const T& b) { return a = std::min(a, b), a == b; }template <typename T>bool chmax(T& a, const T& b) { return a = std::max(a, b), a == b; }template <typename T>std::vector<T> Vec(const std::size_t n, T v) { return std::vector<T>(n, v); }template <class... Args>auto Vec(const std::size_t n, Args... args) { return std::vector<decltype(Vec(args...))>(n, Vec(args...)); }template <typename T>constexpr T popCount(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : (T)__builtin_popcountll(u);#elseunsigned long long v = static_cast<unsigned long long>(u);return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v= (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<T>(v * 0x0101010101010101ULL >> 56 & 0x7f);#endif}template <typename T>constexpr T log2p1(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : T(64 - __builtin_clzll(u));#elseunsigned long long v = static_cast<unsigned long long>(u);return v = static_cast<unsigned long long>(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32),popCount(v);#endif}template <typename T>constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); }template <typename T>constexpr T msbp1(const T v) { return log2p1(v); }template <typename T>constexpr T lsbp1(const T v){#ifdef __has_builtinreturn __builtin_ffsll(v);#elsereturn v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1);#endif}template <typename T>constexpr bool ispow2(const T v) { return popCount(v) == 1; }template <typename T>constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); }template <typename T>constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); }//!=====================================================!////! 8888ba.88ba dP oo !////! 88 '8b '8b 88 !////! 88 88 88 .d8888b. d8888P 88d888b. dP dP. .dP !////! 88 88 88 88' '88 88 88' '88 88 '8bd8' !////! 88 88 88 88. .88 88 88 88 .d88b. !////! dP dP dP '88888P8 dP dP dP dP' 'dP !////!=====================================================!//template <typename T>struct Matrix{Matrix(const std::size_t R, const std::size_t C) : R{R}, C{C}, table(R, std::vector<T>(C, T(0))) {}const std::vector<T>& operator[](const std::size_t r) const { return table[r]; }std::vector<T>& operator[](const std::size_t r) { return table[r]; }Matrix<T> operator-() const{Matrix<T> ans(R, C);for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < C; j++) { ans[i][j] = -table[i][j]; }}return ans;}Matrix<T> operator+(const Matrix<T>& m) const{assert(R == m.R);assert(C == m.C);Matrix<T> ans(R, C);for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < C; j++) { ans[i][j] = table[i][j] + m[i][j]; }}return ans;}Matrix<T> operator-(const Matrix<T>& m) const{assert(R == m.R);assert(C == m.C);Matrix<T> ans(R, C);for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < C; j++) { ans[i][j] = table[i][j] - m[i][j]; }}return ans;}Matrix<T> operator*(const Matrix<T>& m) const{assert(C == m.R);Matrix<T> ans(R, m.C);for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < m.C; j++) {for (std::size_t k = 0; k < C; k++) { ans[i][j] += table[i][k] * m[k][j]; }}}return ans;}Matrix<T> operator*(const T& t) const{Matrix<T> ans(R, C);for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < C; j++) { ans[i][j] = table[i][j] * t; }}return ans;}template <typename C>Matrix<T> operator^(const C n) const { return assert(n > 0), n == 1 ? *this : n % 2 == 1 ? (*this) * ((*this) ^ (n - 1)) : (((*this) * (*this)) ^(n / 2)); }Matrix<T>& operator=(const Matrix<T>& m){assert(R == m.R);assert(C == m.C);for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < C; j++) { table[i][j] = m[i][j]; }}return *this;}Matrix<T>& operator+=(const Matrix<T>& m){assert(R == m.R);assert(C == m.C);for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < C; j++) { table[i][j] += m[i][j]; }}}Matrix<T>& operator-=(const Matrix<T>& m){assert(R == m.R);assert(C == m.C);for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < C; j++) { table[i][j] -= m[i][j]; }}return *this;}Matrix<T>& operator*=(const Matrix<T>& m) { return *this = (*this) * m; }Matrix<T>& operator*=(const T& t){for (std::size_t i = 0; i < R; i++) {for (std::size_t j = 0; j < C; j++) { table[i][j] *= t; }}return *this;}template <typename C>Matrix<T>& operator^=(const C n) { return (*this) = ((*this) ^ n); }const std::size_t R, C;std::vector<std::vector<T>> table;};template <typename T>Matrix<T> operator*(const T& t, const Matrix<T>& m) { return m * t; }template <typename T>std::ostream& operator<<(std::ostream& os, const Matrix<T>& m){os << "[\n";for (std::size_t i = 0; i < m.R; i++) {os << "[";for (std::size_t j = 0; j < m.C; j++) { os << m[i][j] << " "; }os << "]\n";}return (os << "]\n");}template <typename T>struct Vector{Vector(const std::size_t R) : R{R}, table(R, T(0)) {}const T& operator[](const std::size_t r) const { return table[r]; }T& operator[](const std::size_t r) { return table[r]; }Vector<T> operator+(const Vector<T>& v) const{assert(R == v.R);Vector<T> ans(R);for (std::size_t i = 0; i < R; i++) { ans[i] = table[i] + v[i]; }return ans;}Vector<T> operator-(const Vector<T>& v) const{assert(R == v.R);Vector<T> ans(R);for (std::size_t i = 0; i < R; i++) { ans[i] = table[i] - v[i]; }return ans;}Vector<T> operator*(const T& t) const{Vector<T> ans(R);for (std::size_t i = 0; i < R; i++) { ans[i] = table[i] * t; }return ans;}Vector<T>& operator=(const Vector<T>& v){assert(R == v.R);for (std::size_t i = 0; i < R; i++) { table[i] = v[i]; }return *this;}Vector<T>& operator+=(const Vector<T>& v){assert(R == v.R);for (std::size_t i = 0; i < R; i++) { table[i] += v[i]; }return *this;}Vector<T>& operator-=(const Vector<T>& v){assert(R == v.R);for (std::size_t i = 0; i < R; i++) { table[i] -= v[i]; }return *this;}Vector<T>& operator*=(const T& t){Vector<T> ans(R);for (std::size_t i = 0; i < R; i++) { table[i] *= t; }return *this;}const std::size_t R;std::vector<T> table;};template <typename T>Vector<T> operator*(const T& t, const Vector<T>& v) { return v * t; }template <typename T>Vector<T> operator*(const Matrix<T>& m, const Vector<T>& v){assert(m.C == v.R);Vector<T> ans(m.R);for (std::size_t i = 0; i < m.R; i++) {for (std::size_t j = 0; j < m.C; j++) { ans[i] += m[i][j] * v[j]; }}return ans;}template <typename T>std::ostream& operator<<(std::ostream& os, const Vector<T>& v){os << "[\n";for (std::size_t i = 0; i < v.R; i++) { os << v[i] << "\n"; }return (os << "]\n");}template <typename T>struct TVector{TVector(const std::size_t C) : C{C}, table(C, T(0)) {}const T& operator[](const std::size_t c) const { return table[c]; }T& operator[](const std::size_t c) { return table[c]; }TVector<T> operator+(const TVector<T>& v) const{assert(C == v.C);TVector<T> ans(C);for (std::size_t i = 0; i < C; i++) { ans[i] = table[i] + v[i]; }return ans;}TVector<T> operator-(const TVector<T>& v) const{assert(C == v.C);TVector<T> ans(C);for (std::size_t i = 0; i < C; i++) { ans[i] = table[i] - v[i]; }return ans;}TVector<T> operator*(const T& t) const{TVector<T> ans(C);for (std::size_t i = 0; i < C; i++) { ans[i] = table[i] * t; }return ans;}TVector<T>& operator=(const TVector<T>& v){assert(C == v.C);for (std::size_t i = 0; i < C; i++) { table[i] = v[i]; }return *this;}TVector<T>& operator+=(const TVector<T>& v){assert(C == v.C);for (std::size_t i = 0; i < C; i++) { table[i] += v[i]; }return *this;}TVector<T>& operator-=(const TVector<T>& v){assert(C == v.C);for (std::size_t i = 0; i < C; i++) { table[i] -= v[i]; }return *this;}TVector<T>& operator*=(const T& t){TVector<T> ans(C);for (std::size_t i = 0; i < C; i++) { table[i] *= t; }return *this;}const std::size_t C;std::vector<T> table;};template <typename T>TVector<T> operator*(const T& t, const TVector<T>& v) { return v * t; }template <typename T>TVector<T> operator*(const TVector<T>& v, const Matrix<T>& m){assert(v.C == m.R);TVector<T> ans(m.C);for (std::size_t i = 0; i < m.C; i++) {for (std::size_t j = 0; j < m.R; j++) { ans[i] += v[j] * m[j][i]; }}return ans;}template <typename T>std::ostream& operator<<(std::ostream& os, const TVector<T>& v){os << "[ ";for (std::size_t i = 0; i < v.C; i++) { os << v[i] << " "; }return (os << "]\n");}//!=========================================!////! 888888ba dP !////! 88 '8b 88 !////! a88aaaa8P' .d8888b. 88d888b. 88 .dP !////! 88 '8b. 88' '88 88' '88 88888" !////! 88 88 88. .88 88 88 88 '8b. !////! dP dP '88888P8 dP dP dP 'YP !////!=========================================!//template <typename T>std::size_t Rank(Matrix<T> mat){std::size_t r = 0;for (std::size_t c = 0; c < mat.C; c++) {if (r == mat.R) { return r; }std::size_t piv = r;for (; piv < mat.R and mat[piv][c] == 0; piv++) {}if (piv == mat.R) { continue; }std::swap(mat[piv], mat[r]);for (std::size_t j = c + 1; j < mat.C; j++) { mat[r][j] /= mat[r][c]; }for (std::size_t j = r + 1; j < mat.R; j++) {for (std::size_t k = c + 1; k < mat.C; k++) { mat[j][k] -= mat[r][k] * mat[j][c]; }}r++;}return r;}//!===============================================================!////! 88888888b dP .88888. a88888b. 888888ba !////! 88 88 d8' '88 d8' '88 88 '8b !////! a88aaaa dP. .dP d8888P 88 88 88 88 !////! 88 '8bd8' 88 88 YP88 88 88 88 !////! 88 .d88b. 88 Y8. .88 Y8. .88 88 .8P !////! 88888888P dP' 'dP dP '88888' Y88888P' 8888888P !////!===============================================================!//template <typename T>constexpr std::pair<T, T> extgcd(const T a, const T b){if (b == 0) { return std::pair<T, T>{1, 0}; }const auto p = extgcd(b, a % b);return {p.second, p.first - p.second * (a / b)};}template <typename T>constexpr T inverse(const T a, const T mod) { return (mod + extgcd((mod + a % mod) % mod, mod).first % mod) % mod; }//!========================================================!////! 8888ba.88ba dP dP dP !////! 88 '8b '8b 88 88 88 !////! 88 88 88 .d8888b. .d888b88 88 88d888b. d8888P !////! 88 88 88 88' '88 88' '88 88 88' '88 88 !////! 88 88 88 88. .88 88. .88 88 88 88 88 !////! dP dP dP '88888P' '88888P8 dP dP dP dP !////!========================================================!//template <uint mod>class ModInt{private:uint v;static uint norm(const uint& x) { return x < mod ? x : x - mod; }static ModInt make(const uint& x){ModInt m;return m.v = x, m;}static ModInt power(ModInt x, ll n){ModInt ans = 1;for (; n; n >>= 1, x *= x) {if (n & 1) { ans *= x; }}return ans;}static ModInt inv(const ModInt& x) { return ModInt{inverse((ll)x.v, (ll)mod)}; }public:ModInt() : v{0} {}ModInt(const ll val) : v{norm(uint(val % (ll)mod + (ll)mod))} {}ModInt(const ModInt<mod>& n) : v{n()} {}explicit operator bool() const { return v != 0; }ModInt<mod>& operator=(const ModInt<mod>& n) { return v = n(), (*this); }ModInt<mod>& operator=(const ll val) { return v = norm(uint(val % (ll)mod + (ll)mod)), (*this); }ModInt<mod> operator+() const { return *this; }ModInt<mod> operator-() const { return make(norm(mod - v)); }ModInt<mod> operator+(const ModInt<mod>& val) const { return make(norm(v + val())); }ModInt<mod> operator-(const ModInt<mod>& val) const { return make(norm(v + mod - val())); }ModInt<mod> operator*(const ModInt<mod>& val) const { return make((uint)((ll)v * val() % (ll)mod)); }ModInt<mod> operator/(const ModInt<mod>& val) const { return *this * inv(val()); }ModInt<mod>& operator+=(const ModInt<mod>& val) { return *this = *this + val; }ModInt<mod>& operator-=(const ModInt<mod>& val) { return *this = *this - val; }ModInt<mod>& operator*=(const ModInt<mod>& val) { return *this = *this * val; }ModInt<mod>& operator/=(const ModInt<mod>& val) { return *this = *this / val; }ModInt<mod> operator+(const ll val) const { return ModInt{v + val}; }ModInt<mod> operator-(const ll val) const { return ModInt{v - val}; }ModInt<mod> operator*(const ll val) const { return ModInt{(ll)v * (val % mod)}; }ModInt<mod> operator/(const ll val) const { return ModInt{(ll)v * inv(val)}; }template <typename I>ModInt<mod> operator^(const I n) const { return power(v, n); }ModInt<mod>& operator+=(const ll val) { return *this = *this + val; }ModInt<mod>& operator-=(const ll val) { return *this = *this - val; }ModInt<mod>& operator*=(const ll val) { return *this = *this * val; }ModInt<mod>& operator/=(const ll val) { return *this = *this / val; }template <typename I>ModInt<mod>& operator^=(const I n) { return (*this) = ((*this) ^ n); }bool operator==(const ModInt<mod>& val) const { return v == val.v; }bool operator!=(const ModInt<mod>& val) const { return not(*this == val); }bool operator==(const ll val) const { return v == norm(uint((ll)mod + val % (ll)mod)); }bool operator!=(const ll val) const { return not(*this == val); }uint operator()() const { return v; }};template <uint mod>inline ModInt<mod> operator+(const ll val, const ModInt<mod>& n) { return n + val; }template <uint mod>inline ModInt<mod> operator-(const ll val, const ModInt<mod>& n) { return ModInt<mod>{val - (ll)n()}; }template <uint mod>inline ModInt<mod> operator*(const ll val, const ModInt<mod>& n) { return n * val; }template <uint mod>inline ModInt<mod> operator/(const ll val, const ModInt<mod>& n) { return ModInt<mod>(val) / n; }template <uint mod>inline bool operator==(const ll val, const ModInt<mod>& n) { return n == val; }template <uint mod>inline bool operator!=(const ll val, const ModInt<mod>& n) { return not(val == n); }template <uint mod>inline std::istream& operator>>(std::istream& is, ModInt<mod>& n){uint v;return is >> v, n = v, is;}template <uint mod>std::ostream& operator<<(std::ostream& os, const ModInt<mod>& n) { return (os << n()); }//!============================================!////! 8888ba.88ba oo !////! 88 '8b '8b !////! 88 88 88 .d8888b. dP 88d888b. !////! 88 88 88 88' '88 88 88' '88 !////! 88 88 88 88. .88 88 88 88 !////! dP dP dP '88888P8 dP dP dP !////!============================================!//int main(){using Mat = Matrix<ModInt<2>>;int N, M, X;std::cin >> N >> M >> X;Mat mat(M + 30, N + 1);for (int j = 0; j < N; j++) {int A;std::cin >> A;for (int i = 0; i < 30; i++) { mat[i][j] = (A & (1 << i)) != 0; }}std::vector<int> T(M);for (int i = 30; i < M + 30; i++) {int l, r;std::cin >> T[i - 30] >> l >> r;for (int j = l - 1; j < r; j++) { mat[i][j] = 1; }}const int rank1 = Rank(mat);for (int i = 0; i < 30; i++) { mat[i][N] = (X & (1 << i)) != 0; }for (int i = 30; i < M + 30; i++) { mat[i][N] = T[i - 30]; }const int rank2 = Rank(mat);if (rank1 != rank2) { return std::cout << 0 << std::endl, 0; }ModInt<MOD> ans = 1;for (int i = 0; i < N - rank1; i++) { ans *= 2; }std::cout << ans << std::endl;return 0;}