概要
かなり余裕ある．
解法
ランダムな 60 bit の非負整数 $a[0], \ldots, a[N-1]$ を用意します．
01 列 $S$ の値は，$S[i]=1$ であるような $i$ に対する $a[i]$ の総XOR であるとします．
使用可能な index だけでこのような $S$ が構築できればよいです．ランダム行列 $(110,60)$ 行列がフルランクになる確率はきわめて $1$ に近いため，このような $S$ はほぼ常にとることが可能です．
もともと選んだ 150 個が次の性質を満たすならば決定的に解けているということになります：どの 110 個を選んでも全空間を span する．
ランダムベクトル 150 個はたぶんほぼ常にこれを満たすので決定的に解けていると思うのですが，検証していません．
