Description：

问有多少 $n$ 的排列有恰好 $k$ 个位置 $|p_i-i|=1$ 。

$1\leqslant n\leqslant10^3$

Solution：

$DP+$ 容斥的套路。先 $DP$ 出有至少 $k$ 个位置满足条件的方案数，具体做法是设 $f[i][j][0/1][0/1]$ 表示到了第 $i$ 位，已经有至少 $j$ 个这样的位置，当前这个数字是否用过，下一个数字是否用过，然后枚举这一位选前一个 $/$ 选后一个 $/$ 不选分别转移。容斥的话也是套路，系数是组合数。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 1010

int f[MAXN][MAXN][2][2];

int g[MAXN];

int C[MAXN][MAXN];

int fac[MAXN];

#define MOD 1000000007

void updata(int &x,int y){x = (x + y % MOD) % MOD;return;}

int main()

{

	scanf("%d%d",&n,&k);

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	f[0][0][1][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 0;j <= n;++j)

		{

			updata(f[i][j][0][0],(f[i - 1][j][0][0] + f[i - 1][j][1][0]) % MOD);

			updata(f[i][j][1][0],(f[i - 1][j][0][1] + f[i - 1][j][1][1]) % MOD);

			updata(f[i][j + 1][0][0],f[i - 1][j][0][0]);

			updata(f[i][j + 1][1][0],f[i - 1][j][0][1]);

			updata(f[i][j + 1][0][1],f[i - 1][j][0][0] + f[i - 1][j][1][0]);

			updata(f[i][j + 1][1][1],f[i - 1][j][0][1] + f[i - 1][j][1][1]);

		}

	}

	for(int i = 0;i <= n;++i)

	{

		g[i] = 1ll * (f[n][i][0][0] + f[n][i][1][0]) % MOD * fac[n - i] % MOD;

	}

	for(int i = 1;i <= n;++i)

	{

		C[i][0] = C[i][i] = 1;

		for(int j = 1;j < i;++j)

		{

			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;

		}

	}

	int ans = g[k];

	for(int p = k + 1;p <= n;++p)

	{

		ans = (ans + (1ll * (((p - k) & 1) ? -1 : 1) * C[p][k] * g[p] % MOD) + MOD) % MOD;

	}

	cout << ans << endl;

	return 0;

}