結果
問題 |
No.3229 Liar Game Comibination
|
ユーザー |
|
提出日時 | 2025-08-08 22:45:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 8,083 bytes |
コンパイル時間 | 6,198 ms |
コンパイル使用メモリ | 332,952 KB |
実行使用メモリ | 30,228 KB |
最終ジャッジ日時 | 2025-08-08 22:45:42 |
合計ジャッジ時間 | 8,859 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
// https://judge.yosupo.jp/submission/275205 #include <algorithm> #include <array> #include <bit> #include <bitset> #include <cassert> #include <cctype> #include <cfenv> #include <cfloat> #include <chrono> #include <cinttypes> #include <climits> #include <cmath> // #include <compare> #include <complex> // #include <concepts> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <initializer_list> #include <iomanip> #include <ios> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <map> #include <memory> #include <new> #include <numbers> #include <numeric> #include <ostream> #include <queue> #include <random> #include <ranges> #include <set> #include <span> #include <sstream> #include <stack> #include <streambuf> #include <string> #include <tuple> #include <type_traits> #include <variant> #include <atcoder/all> // #define int ll #define INT128_MAX (__int128)(((unsigned __int128)1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1) #define INT128_MIN (-INT128_MAX - 1) #define pb push_back #define eb emplace_back #define clock chrono::steady_clock::now().time_since_epoch().count() using namespace std; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> pr) { return os << pr.first << ' ' << pr.second; } template <class T, size_t N> ostream &operator<<(ostream &os, const array<T, N> &arr) { for (size_t i = 0; T x : arr) { os << x; if (++i != N) os << ' '; } return os; } template <class T> ostream &operator<<(ostream &os, const vector<T> &vec) { for (size_t i = 0; T x : vec) { os << x; if (++i != size(vec)) os << ' '; } return os; } template <class T> ostream &operator<<(ostream &os, const set<T> &s) { for (size_t i = 0; T x : s) { os << x; if (++i != size(s)) os << ' '; } return os; } template <class T1, class T2> ostream &operator<<(ostream &os, const map<T1, T2> &m) { for (size_t i = 0; pair<T1, T2> x : m) { os << x; if (++i != size(m)) os << ' '; } return os; } #ifdef DEBUG #define dbg(...) cerr << '(', _do(#__VA_ARGS__), cerr << ") = ", _do2(__VA_ARGS__) template <typename T> void _do(T &&x) { cerr << x; } template <typename T, typename... S> void _do(T &&x, S &&...y) { cerr << x << ", "; _do(y...); } template <typename T> void _do2(T &&x) { cerr << x << endl; } template <typename T, typename... S> void _do2(T &&x, S &&...y) { cerr << x << ", "; _do2(y...); } #else #define dbg(...) #endif using ll = long long; using ull = unsigned long long; using ldb = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; // #define double ldb template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; template <typename T> using max_heap = priority_queue<T>; template <ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP = plus<T>> void pSum(rng &&v) { if (!v.empty()) for (T p = v[0]; T &x : v | views::drop(1)) x = p = OP()(p, x); } template <ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP> void pSum(rng &&v, OP op) { if (!v.empty()) for (T p = v[0]; T &x : v | views::drop(1)) x = p = op(p, x); } template <ranges::forward_range rng> void Unique(rng &v) { ranges::sort(v); v.resize(unique(v.begin(), v.end()) - v.begin()); } template <ranges::random_access_range rng> rng invPerm(rng p) { rng ret = p; for (int i = 0; i < ssize(p); i++) ret[p[i]] = i; return ret; } template <ranges::random_access_range rng, ranges::random_access_range rng2> rng Permute(rng v, rng2 p) { rng ret = v; for (int i = 0; i < ssize(p); i++) ret[p[i]] = v[i]; return ret; } template <bool directed> vector<vector<int>> readGraph(int n, int m, int base) { vector<vector<int>> g(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u -= base, v -= base; g[u].emplace_back(v); if constexpr (!directed) g[v].emplace_back(u); } return g; } template <class T> void setBit(T &msk, int bit, bool x) { msk = (msk & ~(T(1) << bit)) | (T(x) << bit); } template <class T> void flipBit(T &msk, int bit) { msk ^= T(1) << bit; } template <class T> bool getBit(T msk, int bit) { return msk >> bit & T(1); } template <class T> T floorDiv(T a, T b) { if (b < 0) a *= -1, b *= -1; return a >= 0 ? a / b : (a - b + 1) / b; } template <class T> T ceilDiv(T a, T b) { if (b < 0) a *= -1, b *= -1; return a >= 0 ? (a + b - 1) / b : a / b; } template <class T> bool chmin(T &a, T b) { return a > b ? a = b, 1 : 0; } template <class T> bool chmax(T &a, T b) { return a < b ? a = b, 1 : 0; } // rank: size(prs), det: full_rank ? sgn : 0 // inv(LI): L == I ? R : -1 // Ax=b(Ab): b is pivot col ? -1 : x[c] = M[prs[i]].back // where c is pivot column of row prs[i] const int mod = 998244353; auto eliminate(vector<vector<int>> M) { int n = ssize(M), m = M.empty() ? 0 : ssize(M[0]), sgn = 1; vector<int> prs; for (int r = 0, c = 0; r < n and c < m; c++) { int pr = r; while (pr < n and M[pr][c] == 0) pr++; if (pr == n) continue; prs.emplace_back(r); if (r != pr) M[r].swap(M[pr]), sgn = (mod - sgn) % mod; ll inv = 1, b = M[r][c]; sgn = (ll)sgn * b % mod; for (int i = 0; i < 30; i++, b = b * b % mod) if ((mod - 2) >> i & 1) inv = inv * b % mod; for (int i = 0; i < m; i++) M[r][i] = M[r][i] * inv % mod; for (int i = 0; i < n; i++) { if (i == r or M[i][c] == 0) continue; ll x = M[i][c]; for (int j = c; j < m; j++) M[i][j] = (M[i][j] + mod - M[r][j] * x % mod) % mod; } r++; } return tuple(M, prs, sgn); } template <uint32_t m_max = 1> pair<vector<string>, vector<int>> eliminate(vector<string> M) { if (m_max < size(M[0])) return eliminate<min(m_max << 1, 1u << 13)>(std::move(M)); int n = ssize(M), m = ssize(M[0]); vector<bitset<m_max>> N; for (auto &s : M) { ranges::reverse(s); N.emplace_back(s); } vector<int> prs; for (int r = 0, c = 0; r < n and c < m; c++) { int pr = r; while (pr < n and !N[pr][c]) pr++; if (pr == n) continue; prs.emplace_back(r); if (r != pr) swap(N[r], N[pr]); for (int i = 0; i < n; i++) if (i != r and N[i][c]) N[i] ^= N[r]; r++; } for (int i = 0; i < n; i++) { string s = N[i].to_string().substr(m_max - m); ranges::reverse(s); M[i] = s; } return pair(M, prs); } signed main() { ios::sync_with_stdio(false), cin.tie(NULL); int n, m; using lint = long long; lint k; cin >> m >> n >> k; vector<string> a(n); for (auto &s : a) cin >> s; for (auto &s : a) { // char c; // cin >> c; s += '0'; } auto [M, prs] = eliminate(a); string sol(m, '0'); vector<int> mp(n, -1); vector<bool> is_pivot(m, false); for (int i : prs) { int j = M[i].find('1'); if (j == m) { cout << 0 << '\n'; return 0; } if (M[i][m] == '1') sol[j] = '1'; mp[i] = j, is_pivot[j] = true; } cout << atcoder::pow_mod(2, m - ssize(prs), k) << "\n"; // vector<string> basis; // for (int c = 0; c < m; c++) { // if (is_pivot[c]) continue; // string s(m, '0'); // s[c] = '1'; // for (int r = 0; r < n; r++) { // if (M[r][c] == '0') continue; // s[mp[r]] = '1'; // } // basis.eb(s); // } // cout << m - ssize(prs) << '\n'; // cout << sol << '\n'; // for (auto &s : basis) cout << s << '\n'; return 0; }