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; } };