ARC084 F : XorShift(1000)
作成日：2017.11.05
最終更新日：2017.11.05
問題概要
$N$個の整数$A_i$が黒板に書かれている。
黒板に書かれている異なるとは限らない整数$p$,$q$において、$2p$または$p \: xor \: q$を新たに黒板に書き加える操作が許されている。
この操作を繰り返すことで黒板に書かれている状態にできる$X$以下の非負整数の個数を$mod \: 998244353$で求めよ。
制約
$1 \leq N \leq 6$
$1 \leq X < 2^{4000}$
$1 \leq A_i < 2^{4000}$
$X$,$A_i$は2進表記で与えられ、先頭の桁は1である
考え方
$a$に$xor \: b$を2回作用させたものは$a$であるから、$A_i$を$A_i \: xor \: A_j$($i \leq j$)に置き換えても答えは変わらない。
そこで、$A_i$を可能な限り小さくすることを考える。
$A$の中に$0$でないものが2つ以上ある時、そのうちの2つを$s$,$t$($s>t$)とする。
$s$と$t$の桁数が同じ時は($s \: xor \: t$)$< s$が成り立つから、$s$を$s \: xor \: t$に置き換える。
そうでない時も$t$に$2$の累乗をかけたものも黒板に書くことができることから、
$t$に$2$の累乗をかけ$s$と桁数を揃えた$t'$を考えて、$s$を$s \: xor \: t'$に置き換えても答えは変わらない。
桁数が同じ数で$xor$を取ると必ず桁数が減るので、後者の場合も$s$は小さくなっている。
以上のことから、$A$の中に$0$でないものが1つだけある状態にできることが分かる。
よって、$N = 1$の場合に問題が解ければ良い。
まず、$a$と$a$の$2^i$倍の数$a_i$のいくつかを選んで$xor$をとることで$z$が作れるかを判定することを考える。
これは$z \: xor \: a_i$における判定と一致することから、前半の議論と同様にして$z$の桁数を$a$の桁数未満に減らすことができる。
そうした時に$z = 0$である時に限り可能である。
このことから$a$の桁数を$d$とすると、作れる$z$は下位から見て$d$ビット目以降が定まるごとに1つだけであることが分かる。
すなわち答えは$X/2^{d-1}$か$X/2^{d-1} + 1$である。
答えが後者であるのは、下位から見て$d$ビット目以降が$X$と一致する時に作れる数が$X$以下である時だが、これは実際に作って調べれば良い。
桁数の最大値を$D$とすると、前半において1回の演算は$O(D)$、演算の回数は演算ごとに桁が1つ以上減るので$O(ND)$であるから、前半全体の計算量は$O(ND^2)$である。
また、後半の計算量は$O(D)$である。
これらは十分に高速である。
ソースコード
マクロ等はこちら
const int MC = 4010;
const LL mod = 998244353;
int N;
bitset<MC> X;
bitset<MC> A[9],B;
int d[9];
int s[9];
int main(){
cin >> N;
cin >> X;
repp(i,0,N) cin >> A[i];
repp(i,0,N) repp(j,0,MC) if(A[i][j]) d[i] = j;
if(N>1){
repp(i,0,N) s[i] = i;
auto comp = [&](const int p , const int q){return d[p] > d[q];};
sort(s,s+N,comp);
while(d[s[1]] >= 0){
A[s[0]] = (A[s[0]]^(A[s[1]]<<(d[s[0]]-d[s[1]])));
while(d[s[0]] >= 0 && !A[s[0]][d[s[0]]]) --d[s[0]];
sort(s,s+N,comp);
}
A[0] = A[s[0]];
d[0] = d[s[0]];
}
int z = 0;
repp(j,0,MC) if(X[j]) z = j;
LL ans = 0;
repm(i,z,d[0]-1) ans = (ans * 2 + X[i]) % mod;
repm(i,z,d[0]-1) if(B[i]^X[i]) B ^= (A[0]<<(i-d[0]));
++ans;
repm(i,d[0]-1,-1){
if(B[i]^X[i]){
if(B[i]) ans += mod-1;
break;
}
}
cout << ans % mod << endl;
return 0;
}解法まとめ
$xor$をとったものに置き換えることで$A_i$を1つを除いて$0$にする。(14-25行)
下位から見て$d$ビット目以降が$X$と一致する時に$A$から作れる数が$X$以下の時は$X/2^{d-1} + 1$、そうでない時は$X/2^{d-1}$が答えである。(26-37行)