ABC189 E Rotate and Flip
各操作は次のような操作である.
操作1: $ (x,y) -> $ (y,-x)
操作2: $ (x,y) -> $ (-y, x)
操作3: $ (x,y) -> $ (-x + 2p, y)
操作4: $ (x,y) -> $ (x, -y + 2p)
これを次のように変形する. 操作後の$ (x,y)をそれぞれ$ (x', y')として,
操作1: $ x' = 0x + 1y + 0, y' = -1x + 0y + 0
操作2: $ x' = 0x - 1y + 0, y' = 1x + 0y + 0
操作3: $ x' = -1x + 0y + 2p, y' = 0x + 1y + 0
操作4: $ x' = 1x + 0y + 0, y' = 0x - 1y + 2p
このように, $ (x,y)および定数項で新しい$ (x', y')は表せることになる.
よってこのように多項式の形に変換することで, $ (x,y, 定数項)について係数を持っておけばよいことになり, この係数を計算していくことにより高速に求めることができる. 計算量は$ O(N + M + Q)となる.
また, これは行列式として表すこともできる.