AtCoder Beginner Contest 134：F - Permutation Oddness

問題
解法
解答

問題

https://atcoder.jp/contests/abc134/tasks/abc134_f

解法

元の数列 (1, 2, ... , N) と新しく構成した数列（ここでは〇で示している）を縦に並べて，同じ数字同士を線で結んでみる．すると以下のようになる．

*1

問題で問われている奇妙さは画像にある緑の線がそれぞれ結んでいる数の位置の落差になっている．つまり，各段の間に線をひき，これらの線と緑の線が交わる回数が奇妙さになっている．ここで以下の DP を考える．

dp(i, j, k) := i 段目までを見て，j 個の数の位置をまだ決めていなく，確定している奇妙さが k であるときのこれからありうる順列の通り数

まだ線で結んでいないものの数は両側とも j 個で等しくなる．遷移は以下の 4 つのパターンが考えられる．

*2

パターンアは i + 1 段目を線で結ぶ場合，パターンイはどちらも線を結ぶ先を保留する場合，パターンウはどちらか片方だけ線を出す場合，パターンエはどちらも線を出す場合を表している．パターンア，ウでは j の数は変わらないが，パターンイでは +1 され，パターンエでは - 1 される．各パターンで k は両側 j の変動分 * 2 だけ増加する．O(n^2 * k)．