洛谷P1595 信封问题题解错排问题

2024-08-26 01:30:42

作者：zifeiy
标签：排列组合,错排问题

题目链接：https://www.luogu.org/problem/P1595

题目描述：某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。

可以发现，这就是一道纯纯的“错排问题”。

错排问题 是指给你n个数，问：这n个数中有多少种排列是每个位置和原排列中的每个元素都不一样的。

本着不重复造轮子的思想，转载洛谷上介绍错排问题的这篇博客

其中，比较好实现的一种方式是用 \(f[i]\) 来表示 i 个数的全错排方案数，以及递推公式：

f[1] = 0

f[2] = 1

f[i] = (i-1) * (f[i-1] + f[i-2])

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

int n;

long long f[22];

int main() {

    cin >> n;

    f[1] = 0;

    f[2] = 1;

    for (int i = 3; i <= n; i ++) f[i] = (i-1) * ( f[i-1] + f[i-2] );

    cout << f[n] << endl;

    return 0;

}

最新文章

热门文章