AtCoder Regular Contest 136

B - Triple Shift

In this construction, parity of the inversion number is an inveriant. ## C - Circular Addition cyclic difference.

E - Non-coprime DAG

DON'T resort to flows, math is the way to go!

try analyze what it means to be connected.

Base on the fact that every pair of even number are connected, and the distance to any number connected to \(x\) is always greater than \(\mathrm{lpf}(x)\). a simple casework reveals the exact constraint.

F - Flip Cells

PGF magic.

Assume the process never ends, let \(F(z)\) be the PGF formoving from initial state to a valid end state, and \(G(z)\) be the PGF for moving from a valid end state to another(note how the initial state is irrelavent here).

We have: \[E(z)G(z)=F(z)\]

where \(E(z)\) is the PGF of the game.

The answer is just \(E'(1)\).

details

derive \(F(z)\) and \(G(z)\)

we first calculate the exponential PGF of \(F\) and \(G\), then wirte them as the sum of a bunch of \(\exp\). Finally substitute \(\exp\) for \(\frac1{1-z}\) to get the ordinary PGF.