P3182 [HAOI2016] 放棋子 题解
August_Light
·
·
题解
P3182 [HAOI2016] 放棋子 题解
题目传送门
题意简述
给你一个 N \times N 的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放 N 枚棋子（障碍的位置不能放棋子），要求你放 N 个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。
## 解法
蓝题？建议评黄。
首先发现矩阵没用。因为完全可以把所有的障碍排在对角线上达到相同效果。
然后发现答案变为长度为 $n$ 的[错排列](https://oi-wiki.org/math/combinatorics/derangement/)数目。
> （摘自 OI Wiki）即，对于 $1\sim n$ 的排列 $P$，如果满足 $P_i\neq i$，则称 $P$ 是 $n$ 的错位排列。
然后想起小学二年级就学过的错排列数目递推式：
$$f_n = \begin{cases} 0 & n = 1 \\ 1 & n = 2 \\ (n-1)(f_{n-1}+f_{n-2}) & n \ge 3 \end{cases}$$
推导过程：
设 $n$ 号元素放在 $i$ 号位置。（$1 \le i \le n-1$）
- 如果 $i$ 号元素放在 $n$ 号位置，则变为 $n-2$ 的子问题。
- 否则变为 $n-1$ 的子问题。
不算高精的话，时间复杂度 $O(n)$，空间复杂度 $O(1)$。
## 代码
因为要高精所以写 python。
```python
def P3182(n: int):
a, b = 0, 1
if n == 1:
return 0
elif n == 2:
return 1
else:
for i in range(3, n+1):
a, b = b, (i-1) * (a+b)
return b
n = int(input())
print(P3182(n))
```
## 双倍经验
[P1595 信封问题](https://www.luogu.com.cn/problem/P1595)