（递推计算组合数）P4071 [SDOI2016]排列计数
吐个槽先：没啥好吐槽的, 就是我自己傻掉了. Orz.
这题的式子非常水.
- 在 \(n\) 个数里面选 \(m\) 个固定, 即 \(\mathrm{C}_n^m\) .
- 再把剩下的 \(n - m\) 个数错序排列, 即 \(h(n - m)\) . 因为只有上面的 \(m\) 个数才能满足 \(i = a_i\) , 下面的 \(n - m\) 个数一定满足 \(i \neq a_i\) .错序排列的递推式为 \(h(x) = (x - 1) * (h(x - 1) + h(x - 2)), h(2) = 1\) .
- 所以总的答案就是 \(\mathrm{C}_n^m \times h(n - m)\) .
本以为能顺利地AC这个题. 但是根据题意, 当 \(n == m\) 时, 其含义为 \(n\) 个数中的所有数都满足 \(i = a_i\) , 显然只有一种情况, 答案应该为 \(1\) , 但是带进去算发现答案是 \(0\) . 原因就是我处理的 \(h(0) = 0\) , 实际上, h(0) 本身就是一个没有意义的东西, 但好像也可以这么理解(不知道对不对): 该序列有 \(0\) 个元素, 我们说这个序列是空序列, 显然在空序列里没有任何一个元素能满足 \(i = a_i\) , 存在唯一一种情况就是这个空序列本身, 答案为 \(1\). 所以我应该处理为 \(h(0) = 1\) .
如有错误, 请各位神指正. Orz.