結果

問題 No.3229 Liar Game Comibination
ユーザー Today03
提出日時 2025-08-10 15:52:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 181 ms / 2,000 ms
コード長 3,835 bytes
コンパイル時間 3,935 ms
コンパイル使用メモリ 288,984 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-08-10 15:52:13
合計ジャッジ時間 6,340 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)

template<typename T> bool chmax(T& a, T b) { return a<b ? a=b, true : false; }
template<typename T> bool chmin(T& a, T b) { return a>b ? a=b, true : false; }
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using WG=vector<vector<pair<int,ll>>>;

#ifdef LOCAL
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif



/// @brief x^n (mod m) を返す
template<typename T=ll>
T ModPow(T x, T n, T mod) {
    T ret=1;
    if(typeid(T)==typeid(ll)&&mod>INF*2) return ModPow<__int128_t>(x,n,mod);
    while(n>0) {
        if(n&1) (ret*=x)%=mod;
        (x*=x)%=mod;
        n>>=1;
    }
    return ret;
}

/// @brief x^(-1) (mod m) を返す
ll ModInv(ll a, ll m) {
    ll b=m,u=1,v=0;
    while(b) {
        ll t=a/b;
        a-=t*b; swap(a,b);
        u-=t*v; swap(u,v);
    }
    return (u+m)%m;
}


/// @brief F_2 上の連立線形方程式
/// @ref https://mathlandscape.com/solution-sp/
/// @ref https://yukicoder.me/submissions/1011997
/// @ref verify:https://yukicoder.me/problems/no/2895

/// @brief 掃き出し法
/// @param a 連立方程式 Ax=b の拡大係数行列
/// @param where ピボットとなる変数を記録するための配列
/// @return A のランク
template<int MAX_COL>
int RowReduction(vector<bitset<MAX_COL>>& a, int col, vector<int>& where) {
    int row=a.size();
    int rank=0;
    for(int c=0; c<col-1; c++) {
        int pivot=rank;
        while(pivot<row && !a[pivot][c]) pivot++;
        if(pivot==row) continue;
        swap(a[pivot],a[rank]);
        where.push_back(c);
        for(int r=0; r<row; r++) {
            if(r!=rank && a[r][c]) a[r]^=a[rank];
        }
        rank++;
    }
    return rank;
}

/// @brief 連立線形方程式 Ax=b を解く
/// @param x0 特殊解(b=0 の場合は自明解になる)
/// @param ker Ax=0 の解空間の基底
/// @note 一般解は x0 と解空間の基底の任意の線形結合で表される
/// @attention A のサイズによっては基底のサイズが巨大になるので注意すること
template<int MAX_COL>
bool LinearEquation(vector<bitset<MAX_COL>> a, vector<bool> b, int col, vector<bool>& x0, vector<vector<bool>>& ker) {
    int row=a.size();
    assert(b.size()==row);

    vector<bitset<MAX_COL>> a2(row);
    for(int i=0; i<row; i++) {
        a2[i].reset();
        for(int j=0; j<col; j++) a2[i][j]=a[i][j];
        if(b[i]) a2[i][col]=true;
    }

    vector<int> where;
    int rank=RowReduction<MAX_COL>(a2,col+1,where);

    for(int r=rank; r<row; r++) if(a2[r][col]) return false;

    x0=vector<bool>(col,false);
    for(int i=0; i<rank; i++) x0[where[i]]=a2[i][col];

    int r=0;
    for(int c=0; c<col; c++) {
        if(r<rank && c==where[r]) {
            r++;
            continue;
        }
        vector<bool> x(col);
        x[c]=true;
        for(int r2=0; r2<r; r2++) x[where[r2]]=a2[r2][c];
        ker.push_back(x);
    }

    return true;
}

//----------------------------------------------------------

void solve() {
    ll N,M,K; cin>>N>>M>>K;

    const int MAX_COL=2500;
    vector<bitset<MAX_COL>> A(M);
    vector<bool> B(M);

    REP(i,M) {
        string S; cin>>S;
        REP(j,MAX_COL-1) A[i][j]=false;
        REP(j,N) if(S[j]=='1') A[i][j]=true;
    }

    vector<bool> x0;
    vector<vector<bool>> ker;
    bool res=LinearEquation<MAX_COL>(A,B,N,x0,ker);

    debug(x0);
    debug(ker);

    cout<<ModPow<ll>(2,ker.size(),K)<<endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout<<fixed<<setprecision(15);
    int T=1;
    //cin>>T;
    while(T--) solve();
}
0