WTF C2 Triangular Lamps Hard 別解法

今回は、Nimberを使ってWTF C Triangular Lamps Easy / Hardを解いていこうと思います。

C1

このような問題では、操作で変わらない不変量を考えたくなります

具体的には $(x, y)$ に $\binom{x + y}{x} \pmod 2$ を書き込めば、 $(x \geq 0, y \geq 0)$ では不変量です。なのでこれを適切にシフトしたものを考えて、うまくやるとOKです

先述の不変量は一般の場合ではあまり役に立ちません。なぜならば、1の数が少なすぎるからです。つまり不変量を求めたところで元の点に関して得られる情報量が少なすぎます。

じゃあどうするかというと、元々の想定解法では先述の不変量を同時に大量にばら撒きます。もちろん適切に計算できるようなばらまきかたをしないといけなくて、そういうことを考えると自然と $\bmod 3$ が出てきます。

今回はもっと情報量の多い不変量を考えることにします。

実際に、ある $a$ について、 $(x, y)$ に $a^ x (a+1)^ y$ を書き込むと、これは不変量になっています。ただし、要素は全て $\mathbb{F}_ {2^N}$ とします。 $\bmod 2$ でダメなら $\mathbb{F}_{2^N}$ というのは自然ですね。

この不変量により、 $a$ を原子根にすると、 $(a + 1) = a^s$ として、 $x + sy$ が求まります。もう一つ、他のaについても調べると、ある $t$ について $x + ty$ が求まります。

結果として、 $x, y$ が求まりました。

実装としては、 $F_{2^N}$ で離散対数を求める必要があります。ところで、最近Nimberで離散対数を求める問題が出ました: Problem - F - Codeforces　ちょうどいいですね。