結果

問題 No.3229 Liar Game Comibination
ユーザー kwm_t
提出日時 2025-08-08 22:31:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,550 bytes
コンパイル時間 5,950 ms
コンパイル使用メモリ 335,140 KB
実行使用メモリ 88,104 KB
最終ジャッジ日時 2025-08-08 22:31:31
合計ジャッジ時間 14,191 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = atcoder::modint;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
#include <vector>
#include <string>
#include <iostream> 

using modint2 = static_modint<2>;
template<typename ModInt>
struct GaussJordan {
	GaussJordan(std::vector<std::vector<ModInt>>_a, std::vector<ModInt>_b) :a(_a), b(_b) {}
	// デバッグ用
	void dbg() {
		int n = a.size();
		int m = a[0].size();
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j)std::cout << a[i][j].val() << " ";
			std::cout << std::endl;
		}
		for (int i = 0; i < n; ++i) std::cout << b[i].val() << " ";
		std::cout << std::endl;
	}
	// 掃き出し法
	int sweep() {
		int n = a.size();
		int m = a[0].size();
		rank = 0;
		for (int i = 0; i < m; ++i) {
			int pivot = -1;
			for (int j = rank; j < n; ++j) {
				if (0 != a[j][i]) {
					pivot = j;
					break;
				}
			}
			if (-1 == pivot)continue;
			ModInt inv = inv_mod(a[pivot][i].val(), ModInt::mod());
			std::swap(a[rank], a[pivot]);
			std::swap(b[rank], b[pivot]);
			for (int j = i; j < m; ++j) a[rank][j] *= inv;
			b[rank] *= inv;
			for (int j = 0; j < n; ++j) {
				if (rank == j)continue;
				if (0 == a[j][i])continue;
				ModInt x = a[j][i];
				for (int k = 0; k < m; ++k) a[j][k] -= x * a[rank][k];
				b[j] -= x * b[rank];
			}
			rank++;
		}
		return rank;
	}
	// Ax= Bなxを１つ求める
	bool solve() {
		int n = a.size();
		int m = a[0].size();
		x.assign(m, 0);
		sweep();
		for (int i = rank; i < n; ++i)if (0 != b[i].val()) return false;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (0 != a[i][j]) {
					x[j] = b[i];
					break;
				}
			}
		}
		return true;
	}
	// 核
	std::vector<std::vector<ModInt>> kernel() {
		int n = a.size();
		int m = a[0].size();
		sweep();
		std::vector<int>cols(m, 0), piv;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (1 == a[i][j]) {
					cols[j] = 1;
					piv.push_back(j);
					break;
				}
			}
		}
		ker.clear();
		for (int i = 0; i < m; ++i) {
			if (cols[i])continue;
			std::vector<ModInt>v(m);
			v[i] = -1;
			for (int j = 0; j < piv.size(); ++j) v[piv[j]] = a[j][i];
			ker.push_back(v);
		}
		return ker;
	}
	int rank;
	std::vector<std::vector<ModInt>>a;
	std::vector<ModInt>x;
	std::vector<ModInt>b;
	std::vector<std::vector<ModInt>>ker;
};
// how to use
// using modint2 = static_modint<2>;
// vector a(n, vector<modint2>(n));
// vector<modint2>b(n);
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m, k; cin >> n >> m >> k;
	mint::set_mod(k);
	vector a(m, vector<modint2>(n));
	rep(i, m) {
		string s; cin >> s;
		rep(j, n)if (s[j] == '1')a[i][j] = 1;
	}
	vector<modint2>b(m);
	GaussJordan gj(a, b);
	auto rank = gj.sweep();
	int ans = pow_mod(2, n - rank, k);
	cout << ans << endl;
	return 0;
}
0