ICPC2017pre-D.cc

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define INF 2000000000
// #define DEBUG(x) cout << #x << ": " << (x) << endl
// void dpite(vector<int> v){
// 	REP(i,(int)v.size()) cout << v[i] << ' ';
// 	cout << endl;
// }



void solve1(int n, int m, vector<string> b) {
	int ans = 0;
	REP(mask, 1<<n){
		vector<int> cnt(m);
		REP(i,n){
			if((mask>>i)&1){
				REP(j,m){
					if(b[i][j] == '1') {
						cnt[j]++;
					}
				}
			}
		}
		bool f = true;
		REP(i,m){
			if(cnt[i]%2 != 0) f = false;
		}
		if(f){
			int cnt = 0;
			// DEBUG(bitset<10>(mask));
			REP(i,n) cnt += ((mask>>i)&1);
			// DEBUG(cnt);
			ans = max(ans, cnt);
		}
	}
	cout << ans << endl;
}

void solve2(int n, int m, vector<string> b) {
	using vi = vector<int>;
	vector<vi> dp(n+1, vi(1<<(m),-INF));
	vector<int> v(n);
	REP(i,n){
		v[i] = 0;
		REP(j,m){
			v[i] <<= 1;
			v[i] += (b[i][j]-'0');
		}
	}
	dp[0][0] = 0;
	REP(i,n){
		dp[i+1] = dp[i];
		REP(j,(int)dp[i].size()){
			dp[i+1][j^v[i]] = max(dp[i+1][j^v[i]],dp[i][j]+1);
		}
	}
	// REP(i,n+1) dpite(dp[i]);
	cout << dp[n][0] << endl;
}

int main() {
	int n,m;
	while(cin >> n >> m and n != 0) {
		vector<string> b(n);
		REP(i,n) cin >> b[i];
		if(n <= 23) {
			solve1(n,m,b);
		}else{
			solve2(n,m,b);
		}
		// solve2(n, m, b);
	}
}