300 字
2 分钟
错排问题

考虑这样的一个问题,n个人互相送礼物,要求礼物不能留给自己,最后会有多少种方案数?

思路#

我们发现直接求解析式很难,需要用到容斥原理,因此我们考虑求递推公式, 令f(n)f(n)为n个人互相送礼物的方案数.我们考虑第一个人a会如何送出手中的礼物.显然除自己外a有n-1种送出礼物的方案,假设送给了b,那么b有几种送礼物的方案呢?

  1. 送给a,那么剩下还要n-2个人的礼物需要处理,即f(n−2)f(n-2)种方案数
  2. 不送给a,这时候不妨把a的位置看作b的位置,也就变成了n-1个人的错排问题,共有f(n−1)f(n-1)种方案数 综上,递推公式为f(n)=(n−1)∗(f(n−2)+f(n−1))f(n)=(n-1)*(f(n-2)+f(n-1)) 易得f(1)=0,f(2)=1f(1)=0,f(2)=1,直接进行递推即可

模板题#

CSES Christmas Party 代码

auto cal = [&](auto &&self, int n) -> ll {
if (n == 1)
return 0;
if (n == 2)
return 1;
if (f[n])
return f[n];
return f[n] = (n - 1) * ((self(self, n - 1) + self(self, n - 2)) % mod) % mod;
};
cin >> n;
cout << cal(cal, n);
错排问题
https://sanzenin.top/posts/obsidian/错排问题/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取