結果

問題 No.3229 Liar Game Comibination
ユーザー kwm_t
提出日時 2025-08-08 22:42:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 212 ms / 2,000 ms
コード長 4,259 bytes
コンパイル時間 4,657 ms
コンパイル使用メモリ 335,132 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-08 22:42:44
合計ジャッジ時間 7,145 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

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 sweep(vector<vector<long long>>a) {
	int n = a.size();
	int m = a[0].size() * 63;
	int rank = 0;
	for (int i = 0; i < m; ++i) {
		int p = i / 63;
		int q = i % 63;
		int pivot = -1;
		for (int j = rank; j < n; ++j) {
			if (0 != (1 & (a[j][p] >> q))) {
				pivot = j;
				break;
			}
		}
		if (-1 == pivot)continue;
		std::swap(a[rank], a[pivot]);
		for (int j = 0; j < n; ++j) {
			if (rank == j)continue;
			if (0 == (1 & (a[j][p] >> q)))continue;
			for (int k = 0; k < a[0].size(); ++k) a[j][k] ^= a[rank][k];
		}
		rank++;
	}
	return rank;
}
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<long long>());
	rep(i, m) {
		string s; cin >> s;
		int idx = 0;
		long long x = 0;
		rep(j, n) {
			x *= 2;
			if (s[j] == '1')x++;
			if ((j + 1) % 63 == 0 || j == n - 1) {
				a[i].push_back(x);
				x = 0;
			}
		}
	}
	auto rank = sweep(a);
	//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