专栏文章

CF285E - Positions in Permutations 分析

hhigh_sky
CF285E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8mgun
此快照首次捕获于
2025/12/01 22:21
3 个月前
此快照最后确认于
2025/12/01 22:21
3 个月前
查看原文

题目概述

对于一个 nn 的排列 pp 定义好位置为满足 ∣pi−i∣=1|p_i-i|=1 的位置，问恰好为 kk 个好位置的方案。

分析

一看到这道题目，就感觉跟[AGC005D] ~K Perm Counting一样。
考虑容斥，设 F(m)F(m) 表示钦定了 mm 个好位置剩下随便排的方案，G(m)G(m) 表示恰好为 mm 个好位置。
那么根据二项式反演可以得到：
G(m)=∑i=mn(−1)i−m(im)F(i)G(m)=\sum_{i=m}^n(-1)^{i-m}\binom{i}{m}F(i)
考虑怎么求 F(m)F(m)。
直接沿用那道题目的分成两部图的方法，然后进行连边，具体而言是左边的 ii 连向右边的 i−1i-1 和 i+1i+1，可以将左边的看作位置，右边的看作 pip_i。
然后我们会依照连边拉出来两条边的数量为 n−1n-1 的链，其实这样就可以直接 dpdp 了，但是我们不要，我们用组合数学的方法。
发现这两条链可以分别处理并且都是互不影响的，所以我们先关注一条链。
我们不能选择两条相邻的边，因为这样会导致他不知道在那个位置，这也就转化成了拥有 n−1n-1 条边的链选择 kk 条不相邻的边的方案数是多少。
我们考虑我们选择的序列为 aa（长度为 kk），那么他需要满足：对于任意 i≥2,ai+1≥ai+2i\geq 2,a_{i+1}\geq a_i+2。
发现这个约束不好做，转化成相差为一的，套路地令 bi←ai−(i−1)b_i\leftarrow a_i-(i-1)，那么 bb 满足：1≤b1<b2<⋯<bk≤n−(k−1)=n−k+11\leq b_1<b_2<\dots<b_k\leq n-(k-1)=n-k+1。
这相当于在 11 到 n−k+1n-k+1 这些数选择 kk 个，最后排序就是 bb 了。
综上所述，拥有 n−1n-1 条边的链选择 kk 条不相邻的边的方案数为 (n−k+1k)\binom{n-k+1}{k}。
我们现在要将两条链组合起来，设 fmf_m 表示总共选 mm 条边的方案。
那么显然有：fm=∑i=0m(n−1−i+1i)(n−1−(m−i)+1m−i)f_m=\sum_{i=0}^m\binom{n-1-i+1}{i}\binom{n-1-(m-i)+1}{m-i}。
那么有：F(m)=fm(n−m)!F(m)=f_m(n-m)!。
然后反演求出 G(m)G(m) 即可。

代码

时间复杂度 O(n2)\mathcal{O}(n^2)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...