結果
問題 | No.803 Very Limited Xor Subset |
ユーザー |
![]() |
提出日時 | 2019-03-18 12:43:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 4,545 bytes |
コンパイル時間 | 1,143 ms |
コンパイル使用メモリ | 112,200 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 06:35:08 |
合計ジャッジ時間 | 2,819 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
// #define _GLIBCXX_DEBUG // for STL debug (optional) #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> #include <bitset> using namespace std; #define debug(...) fprintf(stderr, __VA_ARGS__) #define int long long int template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chadd(T &a, T b) {a = a + b;} typedef pair<int, int> pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 1000000007LL; // 行列ライブラリ // Verified: TopCoder SRM 704 Div.2 (ModEquationEasy) // 行列の積 と 累乗(繰り返し二乗法) // Matrix Library Begin (C++11) template <typename T> using Matrix = vector< vector<T> >; template <typename T> void init_mat(Matrix<T> &A, int h, int w) { A.resize(h, vector<T>(w, 0)); } template <typename T> Matrix<T> calc_mat(Matrix<T> A, Matrix<T> B) { Matrix<T> C(A.size(), vector<T>(B[0].size())); for(int i=0; i<A.size(); i++) { for(int k=0; k<B.size(); k++) { for(int j=0; j<B[0].size(); j++) { // C[i][j] += A[i][k] * B[k][j]; // modなし C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; // modあり } } } return C; } template <typename T> Matrix<T> mat_pow(Matrix<T> A, ll n) { Matrix<T> B(A.size(), vector<T>(A.size())); for(int i=0; i<A.size(); i++) B[i][i] = 1; while(n > 0) { if(n & 1) B = calc_mat(B, A); A = calc_mat(A, A); n >>= 1; } return B; } // N * M 行列のランクを求める // 整数行列でも基本変形時に分数になるので double 型に限定しています // 位数 2 の有限体では (演算を xor とかに直した形で) 確認済み、他は未 Verify なのでもしかしたらやばいかもしれない int mat_rank(Matrix<int> A) { int N = A.size(), M = A[0].size(); int res = 0; for(int i=0; i<M-1; i++) { // 絶対値が最も大きいものを探す int max_elem = 0; int piv = -1; for(int j=res; j<N; j++) { if(abs(A[j][i]) > max_elem) { max_elem = abs(A[j][i]); piv = j; } } // res 行目を piv 行目に変えて、行基本変形 if(piv < 0) continue; swap(A[res], A[piv]); // res 行目を正規化 // F_2 の場合はここは不要 /* { double div = A[res][i]; for(int k=0; k<M; k++) { A[res][k] = 1.0 * A[res][k] / div; } } */ for(int j=0; j<N; j++) { if(j == res) continue; assert(A[res][i] != 0); int mul = A[j][i]; for(int k=0; k<M; k++) { // 場合に応じて xor に変えるなりする // A[j][k] = A[j][k] - mul * A[res][k]; A[j][k] = A[j][k] ^ (mul * A[res][k]); } } res++; } for(int i=res; i<N; i++) if(A[i][M-1]) return -1; return res; } // Matrix Library End signed main() { int N, M, X; cin >> N >> M >> X; Matrix<int> mat; const int B = 30; init_mat(mat, B+M, N+1); for(int j=0; j<30; j++) { int p = X & 1; mat[j][N] = p; X >>= 1; } for(int i=0; i<N; i++) { int val; cin >> val; for(int j=0; j<30; j++) { int p = val & 1; mat[j][i] = p; val >>= 1; } } for(int i=0; i<M; i++) { int t, l, r; cin >> t >> l >> r; l--; mat[B+i][N] = t; for(int x=l; x<r; x++) { mat[B+i][x] = 1; } } /* for(int i=0; i<B+M; i++) { for(int j=0; j<N+1; j++) { fprintf(stderr, "%lld ", mat[i][j]); } fprintf(stderr, "\n"); } */ int rank = mat_rank(mat); if(rank < 0) { cout << 0 << endl; return 0; } rank = N - rank; int ans = 1; for(int i=0; i<rank; i++) (ans *= 2) %= MOD; cout << ans << endl; return 0; }