概要
略。
解法
この問題は、150 * 60の$\mathbb{F}_2$ matrixであって、「行ベクトルを110個選んだときに、どう選んでもrankが60になる」ような行列を構築すれば解ける。
ところで、
https://arxiv.org/pdf/1404.3250.pdf
を見ると、ランダムに110 * 60選んだ行列がフルランクになる確率は$(1 - 1/{2^{51}})^{60}$以上らしい。
よって、テストケース数を30とすると失敗する確率は
$1/{2^{51}} * 60 * 30 * 1000$で抑えられ、これはEPS
実装
脳内AC