CF285E - Positions in Permutations 分析

· · 题解

题目概述

对于一个 n 的排列 p 定义好位置为满足 |p_i-i|=1 的位置，问恰好为 k 个好位置的方案。

分析

一看到这道题目，就感觉跟[AGC005D] ~K Perm Counting一样。

考虑容斥，设 F(m) 表示钦定了 m 个好位置剩下随便排的方案，G(m) 表示恰好为 m 个好位置。

那么根据二项式反演可以得到：

G(m)=\sum_{i=m}^n(-1)^{i-m}\binom{i}{m}F(i)

考虑怎么求 F(m)。

直接沿用那道题目的分成两部图的方法，然后进行连边，具体而言是左边的 i 连向右边的 i-1 和 i+1，可以将左边的看作位置，右边的看作 p_i。

然后我们会依照连边拉出来两条边的数量为 n-1 的链，其实这样就可以直接 dp 了，但是我们不要，我们用组合数学的方法。

发现这两条链可以分别处理并且都是互不影响的，所以我们先关注一条链。

我们不能选择两条相邻的边，因为这样会导致他不知道在那个位置，这也就转化成了拥有 n-1 条边的链选择 k 条不相邻的边的方案数是多少。

我们考虑我们选择的序列为 a（长度为 k），那么他需要满足：对于任意 i\geq 2,a_{i+1}\geq a_i+2。

发现这个约束不好做，转化成相差为一的，套路地令 b_i\leftarrow a_i-(i-1)，那么 b 满足：1\leq b_1<b_2<\dots<b_k\leq n-(k-1)=n-k+1。

这相当于在 1 到 n-k+1 这些数选择 k 个，最后排序就是 b 了。

综上所述，拥有 n-1 条边的链选择 k 条不相邻的边的方案数为 \binom{n-k+1}{k}。

我们现在要将两条链组合起来，设 f_m 表示总共选 m 条边的方案。

那么显然有：f_m=\sum_{i=0}^m\binom{n-1-i+1}{i}\binom{n-1-(m-i)+1}{m-i}。

那么有：F(m)=f_m(n-m)!。

然后反演求出 G(m) 即可。

代码

时间复杂度 \mathcal{O}(n^2)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 1005
using namespace std;
const int mod = 1e9 + 7;
int jc[N],inv[N];
int C(int a,int b) {
    if (a < 0 || b < 0 || a < b) return 0;
    return jc[a] * inv[b] % mod * inv[a - b] % mod;
}
int f[N];
signed main(){
    jc[0] = jc[1] = inv[0] = inv[1] = 1;
    for (int i = 2;i < N;i ++) jc[i] = jc[i - 1] * i % mod,inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 2;i < N;i ++) inv[i] = inv[i - 1] * inv[i] % mod;
    int n,k;
    cin >> n >> k;
    for (int i = 0;i <= n;i ++)
        for (int j = 0;j <= i;j ++) f[i] = (f[i] + C(n - j,j) * C(n - (i - j),i - j) % mod) % mod;
    int ans = 0;
    for (int i = k,t = 1;i <= n;i ++,t = -t)
        ans = (ans + (t * C(i,k) % mod * f[i] % mod * jc[n - i] % mod + mod) % mod) % mod;
    cout << ans;
    return 0;
}