题解归档 - cf888D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf888D
• 本地来源：problems/cf888D/idea.md
• 题目链接：https://codeforces.com/contest/888/problem/D
• 原始标题：cf888D — Almost Identity Permutations

思路

cf888D — Almost Identity Permutations

题意

统计大小为 $n$ 的排列 $p$，满足至少 $n-k$ 个下标 $i$ 有 $p_i=i$。$4\le n\le 1000$，$1\le k\le 4$。

思路

「至少 $n-k$ 个不动点」等价于「至多 $k$ 个位置 $i$ 满足 $p_i\ne i$」。

因 $k\le 4$，枚举错位个数 $m=0..k$：从 $n$ 个位置中选出 $m$ 个作为「可能错位」的位置，其余 $n-m$ 个强制不动；在这 $m$ 个位置上必须构成 无不动点的排列（错排），否则某个「错位位置」其实是不动点，与划分矛盾。

故答案为
$$\sum_{m=0}^{k} \binom{n}{m}\cdot !m$$
其中 $!m$ 为错排数（$!0=1,!1=0,!2=1,!3=2,!4=9$）。

验证

• 样例：$(4,1)\to1$，$(4,2)\to7$，$(5,3)\to31$，$(5,4)\to76$ 均符合公式。
• stress.py cf888D -n 100 与暴力全排列对拍通过。

复杂度

预处理组合数 $O(n^2)$，求和 $O(k)$。

代码

来源：problems/cf888D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:41:49
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll c[1005][1005];
ll drr[10];
ll n,i,j,k,m,ans;
int main(){
    for(i=0;i<=1000;i++){
        c[i][0]=1;
        for(j=1;j<=i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
    drr[0]=1;
    drr[1]=0;
    drr[2]=1;
    drr[3]=2;
    drr[4]=9;
    cin>>n>>k;
    ans=0;
    for(m=0;m<=k;m++) ans+=c[n][m]*drr[m];
    cout<<ans<<"\n";
    return 0;
}