JOI 春合宿 2017 Broken Device 解法(未検証)

概要

略。

解法

この問題は、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