ACM组合数学中，如何推导和应用错排公式？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1240个文字，预计阅读时间需要5分钟。
题目链接：https://ac.nowcoder.com/acm/contest/54484/B+ 题意非常简单，但数据范围偏大。错误公式 + 首先来推导一下错误公式：$D(n)=n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$设一个函数：$S_i$ 表示一个排列。
题目链接：ac.nowcoder.com/acm/contest/54484/B
题意很简单，但是数据范围偏大。
错排公式
首先来推导一下错排公式：
$$D(n) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$
设一个函数：
$$S_i表示一个排列中p_i = i的方案数$$
那么我们可以知道：
$$D(n) = n! - |\cup_{i=1}^{n}S_i|$$
这个表示所有方案数减去至少有一个位置放对的方案数。
现在来考虑一下如何处理后面这个并集，并集往往是不好求的，而交集会好求很多，所以在求并集的时候我们往往采取容斥原理将一个并集转换成诸多交集的加减运算。
本文共计1240个文字，预计阅读时间需要5分钟。
题目链接：https://ac.nowcoder.com/acm/contest/54484/B+ 题意非常简单，但数据范围偏大。错误公式 + 首先来推导一下错误公式：$D(n)=n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$设一个函数：$S_i$ 表示一个排列。
题目链接：ac.nowcoder.com/acm/contest/54484/B
题意很简单，但是数据范围偏大。
错排公式
首先来推导一下错排公式：
$$D(n) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$
设一个函数：
$$S_i表示一个排列中p_i = i的方案数$$
那么我们可以知道：
$$D(n) = n! - |\cup_{i=1}^{n}S_i|$$
这个表示所有方案数减去至少有一个位置放对的方案数。
现在来考虑一下如何处理后面这个并集，并集往往是不好求的，而交集会好求很多，所以在求并集的时候我们往往采取容斥原理将一个并集转换成诸多交集的加减运算。