今回は、Nimberを使ってWTF C Triangular Lamps Easy / Hardを解いていこうと思います。
C1
このような問題では、操作で変わらない不変量を考えたくなります
具体的にはにを書き込めば、では不変量です。 なのでこれを適切にシフトしたものを考えて、うまくやるとOKです
C2
先述の不変量は一般の場合ではあまり役に立ちません。 なぜならば、1の数が少なすぎるからです。 つまり不変量を求めたところで元の点に関して得られる情報量が少なすぎます。
じゃあどうするかというと、元々の想定解法では先述の不変量を同時に大量にばら撒きます。 もちろん適切に計算できるようなばらまきかたをしないといけなくて、そういうことを考えると自然とが出てきます。
今回はもっと情報量の多い不変量を考えることにします。
実際に、あるについて、にを書き込むと、これは不変量になっています。ただし、要素は全て とします。でダメならというのは自然ですね。
この不変量により、を原子根にすると、として、が求まります。 もう一つ、他のaについても調べると、あるについてが求まります。
結果として、が求まりました。
実装としては、で離散対数を求める必要があります。 ところで、最近Nimberで離散対数を求める問題が出ました: Problem - F - Codeforces ちょうどいいですね。
実装例: Submission #10507304 - World Tour Finals 2019 Open Contest