300 字
2 分钟
错排问题
考虑这样的一个问题,n个人互相送礼物,要求礼物不能留给自己,最后会有多少种方案数?
思路
我们发现直接求解析式很难,需要用到容斥原理,因此我们考虑求递推公式, 令为n个人互相送礼物的方案数.我们考虑第一个人a会如何送出手中的礼物.显然除自己外a有n-1种送出礼物的方案,假设送给了b,那么b有几种送礼物的方案呢?
- 送给a,那么剩下还要n-2个人的礼物需要处理,即种方案数
- 不送给a,这时候不妨把a的位置看作b的位置,也就变成了n-1个人的错排问题,共有种方案数 综上,递推公式为 易得,直接进行递推即可
模板题
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);分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
最后更新于 ,距今已过 74 天
部分内容可能已过时