23秋招留学生通道-第一题-花圃种植(抽象题)

ID: 168

Type: Default

1000ms

256MiB

Difficulty: 9

Uploaded By:

Tags>

华为

No testdata at current.

1.前置知识:错排原理的容斥解法: 错排数 = 所有排列的个数 - 至少存在一个对位的排列个数 + 至少存在两个对位的排列个数 - 至少存在三个对位的排列个数 + ...

即

$$D(n) = n! - C_{n}^{1}(n - 1)! + C_{n}^{2}(n - 2)! -... +(-1)^n C^{n}_{n} 0! $$

2.考虑一个简单情况:当 $n = m$ 这就是一个错排问题。

3.当 $n < m$ 时，显然可以沿用容斥方法得出公式:

#P1162. 23秋招留学生通道-第一题-花圃种植(抽象题)