F[i][j][a][b] 表示前i个数有j个good position 并且在第i位置和第i+1位置的状态是a和b （0表示不是good position 1表示是 good position)而不管其他数如何放置的方案数 于是有转移f[i][j][a][b]->f[i+1][j][b][0] i+1放在前面 f[i][j][0][b]->f[i+1][j+1][b][0] i+1 放在i位置 f[i][j][a][b]->f[i+1][j+1][b][1] i+2 放在i+2位置

最后统计得到 p[i]=sigma f[n][i] 但是注意到这里p[i]满足了有i个good position 的方案数 然后我们需要考虑剩下的n-i个数 让 p[i]*(n-i)! 得到了k 个good position和剩下数的全排列的方案数,但是注意到全排列之后会有更多的 good position.有k个good position的排列会出现C(k,i)次（k>=i) 由于之前的p[k]已经得出 所以减掉 p[k]*C(k,i)就是答案