AtCoder Grand Contest 005: D. ~K Perm Counting

http://agc005.contest.atcoder.jp/tasks/agc005_d

解法

事象A[i]:=|a[i]-i|=Kを使って包除原理を行う。

たとえば K=2 だった場合、それぞれの事象は次のように表せる。

A[1]: a[1]=-1 または 3
A[2]: a[2]=0  または 4 <===
A[3]: a[3]=1  または 5
A[4]: a[4]=2  または 6
A[5]: a[5]=3  または 7
A[6]: a[6]=4  または 8 <===
...

A[2] の発生と A[6] の発生は依存関係があるが、A[2] と A[4] の発生には依存関係はない。一般に依存関係があるのは mod 2K が等しい事象である。

上の例だと、a[2]=4 という選択が a[6] の選択に影響を与える。事象 A[6] に関係するのは A[2] で 4 をとったかどうかの情報だけなので、これを覚えて DP しよう。dp[ pos ][ num event ][ a[pos]=pos+K かどうか ]:=パターン数

遷移は次の 3 通りある。

• 事象 A[i] を発生させない（not A[i] を発生させるという意味ではなく、単に A[i] を無視する）
• 事象 A[i] を発生させ a[i]=i-K にする
• 事象 A[i] を発生させ a[i]=i+K にする

事象 A[i] を発生させない
これは簡単。 $$ dp[i-2K][j][0] \to dp[i][j][0] $$ $$ dp[i-2K][j][1] \to dp[i][j][0] $$

事象 A[i] を発生させ a[i]=i-K にする $$ dp[i-2K][j][0] \to dp[i][j+1][0] $$

dp[i-2K][j][1] からは遷移できない。a[i-2K]=i-K なので。

事象 A[i] を発生させ a[i]=i+K にする $$ dp[i-2K][j][0] \to dp[i][j+1][1] \quad \mathrm{if}\quad i+K<n $$ $$ dp[i-2K][j][1] \to dp[i][j+1][1] \quad \mathrm{if}\quad i+K<n $$

この DP を回すと 2K 個ばらばらの状態で結果が得られる。それらをマージして xp[i] := イベント発生数 i となるようなパターン数 という配列を得る。イベントが i 個発生している場合、すでに i 個の要素の値は確定しているので、残った n-i 個を隙間に埋めればいい。これは (n-i)! 通りある。したがって、答えは次のようにして得られる。

$$ \sum_{i=0}^{n} (-1)^i xp[i] (n-i)! $$

真っ先に OEIS に投げたけど K=1 しか出てこなくて半分諦めてた。解けてよかった。