結果
問題 |
No.3229 Liar Game Comibination
|
ユーザー |
|
提出日時 | 2025-08-08 22:14:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 186 ms / 2,000 ms |
コード長 | 2,192 bytes |
コンパイル時間 | 4,033 ms |
コンパイル使用メモリ | 255,756 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-08 22:15:12 |
合計ジャッジ時間 | 6,647 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; using mint = atcoder::modint; template <size_t MAX_COL> struct BitMatrix{ int H, W; vector<bitset<MAX_COL>> A; BitMatrix(int n) : H(n), W(MAX_COL), A(n) {} const bitset<MAX_COL>& operator[](int k) const { return A[k]; } bitset<MAX_COL>& operator[](int k) { return A[k]; } int gauss_jordan(bool extended = false) { int rank = 0; for(int j = 0; j < W - extended; j++) { int pivot = -1; for(int i = rank; i < H; i++) { if(A[i][j]){ pivot = i; break; } } if(pivot == -1) continue; swap(A[pivot], A[rank]); for (int i = 0 ; i < H ; i++) { if (i != rank && A[i][j]) A[i] ^= A[rank]; } rank++; } return rank; } pair<int, vector<int>> linear_equation(const vector<int>& b) { assert(H == (int)b.size()); for (int i = 0; i < H; i++) A[i][W] = b[i]; int rank = gauss_jordan(true); for (int i = rank; i < H; i++) { if (A[i][W]) return {-1, vector<int>{}}; } vector<int> res(W, 0); for (int i = 0; i < rank; i++) res[i] = A[i][W]; return {rank, res}; } //N次正方行列について行列式を解く int Determinant(int N){ assert(0 <= N && N <= H && N <= W); return (N == gauss_jordan() ); } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int h, w, k; cin >> w >> h >> k; mint::set_mod(k); BitMatrix<2562> Mt(h); vector<int> b(h); string str; for(int y = 0; y < h; y++){ cin >> str; for(int x = 0; x < w; x++){ Mt[y][x] = (str[x] == '1' ? 1 : 0); } } auto [rank, a] = Mt.linear_equation(b); cerr << rank << '\n'; //for(int y = 0; y < h; y++) cerr << Mt[y] << '\n'; for(int i = 0; i < w; i++) cerr << a[i] << (i + 1 == w ? '\n' : ' '); if(rank == -1){ cout << "0\n"; return 0; } cout << mint(2).pow(w - rank).val() << '\n'; }