Statement:
若一个有 \(n\) 个元素的排列 \(P\) 满足对于任意 \(i(1\le n \le n)\) 都有 \(|P_i - i| \ne k\)，则这个排列是合法的。现给定 \(n, k\)， 问有多少个合法的排列。
Solution:
神仙题啊。
考虑容斥。钦定有 \(i\) 个位置不满足条件，即满足 \(|P_i - i| = k\)。
这里有一步关键的转化：我们将每个下标以及元素的值分别看成一个个点，将满足 \(|P_i - i| = k\) 的点连边，组成一个二分图。
如下图：（机房画不了图就偷了一张）(\(k = 1, n = 5\))
像这样的左部点代表的是 \(P\) 中的元素，右部点代表的是位置。此时问题转化为在这张二分图上找出 \(i\) 条没有公共端点的边的方案数。注意到这个图由一条条互不相交的链组成，如果只有一条链，我们可以直接考虑 \(\rm dp\) 算。实际上，即使有多条链，我们依然可以把他们接在一起组成一条链，只是每条原链的链头不能向它的前驱连边。
于是令 \(f_{i,j,0/1}\) 为考虑链上前 \(i\) 个节点，选了 \(j\) 条互不相交的边，并且选/不选 \(i\) 与它的前驱的边。
显然有：
\[f_{i,j,0} = f_{i - 1, j, 0} + f_{i - 1, j, 1} \]\[f_{i,j,1} = f_{i - 1, j - 1, 0} (head[i] = 0 且 j \ne 0) \]其中 \(head[i] = 1/0\) 为 \(i\) 是/否为原图中某一条链的链头。
最后容斥回来就可以了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define id (x + n * pos)
using namespace std;
const int N = 2000 + 10, mod = 924844033;
int n, k, f[2 * N][N][2], tcnt, jc[N];
bool vis[N * 2], head[N * 2];
void dfs(int x, int pos){
if(x > n || vis[id]) return; vis[id] = true;
// cout << x << " " << pos << "\n";
tcnt++; dfs(x + k, pos ^ 1);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k; jc[0] = 1;
for(int i = 1; i <= n; i++){
if(!vis[i]) head[tcnt + 1] = true, dfs(i, 0);
if(!vis[i + n]) head[tcnt + 1] = true, dfs(i, 1);
jc[i] = (jc[i - 1] * i) % mod;
}
f[1][0][0] = 1;
for(int i = 2; i <= tcnt; i++){
for(int j = 0; j <= n; j++){
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % mod;
if((!head[i]) && j) f[i][j][1] = f[i - 1][j - 1][0];
// cout << i << " " << j << " " << f[i][j][0] << " " << f[i][j][1] << "\n";
}
}
int ans = 0;
for(int i = 0; i <= n; i++) ans = (ans + ((i & 1) ? -1 : 1) * (((f[2 * n][i][0] + f[2 * n][i][1]) % mod) * jc[n - i]) % mod + mod) % mod;
cout << ans;
return 0;
}