AtCoder Grand Contest 005

D - ~K Perm Counting

题目大意：

求有多少个\(1\)到\(n\)的排列\(a\)，满足\(\forall 1\le i\le n\to|a_i-i|\not=k\).

\(2\le n\le2000,1\le k\le n-1\).

题解：

令\(f[i]\)表示选择\(i\)个数并决定它们的位置，使得这\(i\)个数都满足\(|a_i-i|=k\)，即\(a_i\)可以是\(i-k\)或\(i+k\)，的方案数。

则由容斥原理可得\(\displaystyle ans=\sum\limits_{i=0}^n f[i]\times(n-i)!\times(-1)^i\).

接下来介绍如何计算\(f[i]\).

将\(1\)到\(n\)按\(\mod{k}\)的余数分组，则不同的组之间相互独立。

对于同组的情况，我们考虑一个dp，令\(g[i][j][mask]\)表示只考虑前\(i\)个数，一共选了\(j\)个数，最右边的两个数是否占用了\(x+k\)位置的状态为\(mask\)的方案数。

则有递归基：

\[g[1][0][0]=1,g[1][1][1]=1\]

以及转移方程：

\[\displaystyle\begin{aligned}g[i][j][0]&=g[i-1][j][0]+g[i-1][j][2]+g[i-1][j-1][0]\\g[i][j][1]&=g[i-1][j-1][0]+g[i-1][j-1][2]\\g[i][j][2]&=g[i-1][j][1]+g[i-1][j][3]+g[i-1][j-1][1]\\g[i][j][3]&=g[i-1][j-1][1]+g[i-1][j-1][3]\end{aligned}\]

令\(getS(i,j)=g[i][j][0]+g[i][j][2]\)，则可以做一个分组背包来计算\(f[i]\)：

枚举\(\mod{k}\)的余数\(x\)，然后枚举这一组选择的数量\(i\)，则背包时应该用\(f[i]+=f[i-j]\times getS(siz[x],i)\)更新，其中\(siz[x]\)为该组的大小。

计算\(g\)部分的时间复杂度为\(O(n^2)\)，空间复杂度为\(O(n^2)\)；计算\(f\)部分的时间复杂度为\(O(n^2)\)，空间复杂度为\(O(n)\)；计算\(ans\)部分的时间复杂度为\(O(n)\)，空间复杂度为\(O(n)\)。

因此，算法总的时间复杂度为\(O(n^2)\)，空间复杂度\(O(n^2)\)。