Particle

競技プログラミングについての雑記

SRM 590 Div1 Med XorCards

全く分からず、Editorial を見ながら通した。
xor なので、GF(2) での連立方程式の解の個数と対応している。解の個数は、2^(自由度) = 2^(n-rank) となっている。
rank を求める必要があり、難しい版の gauss-jordan を実装する必要がある。

#define N 60
vector<ll> a;
int n;
ll lim;

class XorCards {
	public:
	ll rank(vector<ll> &A, int m){
		int cnt = 0;
		rep(i, m){
			ll k = cnt;
			while(k<N-1){
				if(1&(A[k]>>i)) break;
				k++;
			}
			if(1&(A[k]>>i));
			else continue;
			swap(A[cnt], A[k]);
			rep(j, N){
				if(j!=cnt && (1LL&(A[j]>>i))) A[j]^=A[cnt];
			}
			cnt++;
		}
		rep(i, N) if(A[i]==(1LL<<(m))) return -1;
		int res = 0;
		rep(i, N) if(A[i]) res++;
		return res;
	}
	ll calc(ll l, int b){
		vector<ll> c(a);
		rep(i, n) c[i]>>=b;
		c.pb(l);
		vector<ll> A(N, 0);
		for(int i = 0; i < N; i++) rep(j, n+1) A[i] |= (1LL&(c[j]>>i))<<j;
		ll r = rank(A, n);

		return r==-1?0:1LL<<(n-r);
	}
	long long numberOfWays(vector<long long> number, long long limit) {
		a = number; lim = limit;
		n = a.size();
		sort(all(a)); reverse(all(a));
		ll res = calc(lim, 0);
		rep(i, N){
			if(1LL&(lim>>i)) res += calc((lim>>i)^1LL, i);
		}
		return res;
	}
};