#include using namespace std; #define ALL(x) (x).begin(), (x).end() #define REP(i, n) for(ll i=0; i<(ll)(n); i++) template bool chmax(T& a, T b) { return a 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; using VVI=vector; using VL=vector; using VVL=vector; using PL=pair; using VP=vector; using WG=vector>>; #ifdef LOCAL #include "./debug.hpp" #else #define debug(...) #define print_line #endif /// @brief x^n (mod m) を返す template 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 RowReduction(vector>& a, int col, vector& where) { int row=a.size(); int rank=0; for(int c=0; c bool LinearEquation(vector> a, vector b, int col, vector& x0, vector>& ker) { int row=a.size(); assert(b.size()==row); vector> a2(row); for(int i=0; i where; int rank=RowReduction(a2,col+1,where); for(int r=rank; r(col,false); for(int i=0; i x(col); x[c]=true; for(int r2=0; r2>N>>M>>K; const int MAX_COL=2500; vector> A(M); vector 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 x0; vector> ker; bool res=LinearEquation(A,B,N,x0,ker); debug(x0); debug(ker); cout<(2,ker.size(),K)<>T; while(T--) solve(); }