https://beta.atcoder.jp/contests/arc084/tasks/arc084_d
bitの扱いもうちょっとわかってたらもうちょっと早く思いついたかな。
すべての数がある数Pによって構成できることが証明できます。これときPはgcdに他なりません。
なのでgcdをユークリッドの互除法チックなことをして求めればいいです。
Pで構成できる数のうちX以下の数の個数を数え上げるのは簡単なDPでできます。しかし、場合分けをミスってWA。最後+1するかしないかでWAの2WA。
最初は線形代数っぽいし、rank求めるのが本質かなと思ったけど全然違った。
const int N = 4010; ll pow2[4020]; vi bxor(const vi& a, const vi& b) { vi res(N, 0); rep(i, 0, N) res[i] = (a[i] ^ b[i]); return res; } int fbit(const vi& a) { //fbit(0101) = 3 rer(i, N, 0) { if(a[i] == 1) return i + 1; } return 0; } vi shift(const vi& a, int k) { vi res(N, 0); int fa = fbit(a); assert(fa + k <= N); rep(i, 0, fa) { res[i + k] = a[i]; } return res; } bool is_zero(const vi& a) { rep(i, 0, N) { if(a[i]) return false; } return true; } vi gcd(const vi& a, const vi& b) { if(is_zero(b)) return a; vi c = a; while(true) { int fc = fbit(c), fb = fbit(b); if(fc < fb) break; int diff = fc - fb; c = bxor(c, shift(b, diff)); } return gcd(b, c); } vi stobit(const string& str) { vector<int> res(N, 0); int n = sz(str); rep(i, 0, n) { res[n - i - 1] = str[i] - '0'; } return res; } int M; vi X; vi B[10]; void solve() { string str; cin >> M >> str; pow2[0] = 1; rep(i, 1, 4010) pow2[i] = pow2[i - 1] * 2 % mod; X = stobit(str); rep(i, 0, M) { cin >> str; B[i] = stobit(str); } vi g = B[0]; rep(i, 0, M - 1) g = gcd(g, B[i + 1]); int a = fbit(X), b = fbit(g); vi c(N, 0); ll res = 0; rep(i, 0, (a - b + 1)) { if(X[a - i - 1] == 1) { ADD(res, pow2[a - b - i]); if(c[a - i - 1] == 0) c = bxor(c, shift(g, (a - b - i))); } if(X[a - i - 1] == 0 && c[a - i - 1] == 1) { c = bxor(c, shift(g, (a - b - i))); } } rer(i, N, 0) { if(X[i] == 0 && c[i] == 1) { cout << res << "\n"; return; } else if(X[i] == 1 && c[i] == 0) { cout << (res + 1) % mod << "\n"; return; } } cout << (res + 1) % mod << "\n"; }
bitの問題にもっと強くなりたい。
