\[\huge{\color{#ff0000}{\text{被XJK搏杀了，我tcl}}} \]
我们先从\(n\)个数里选\(m\)个数钦定这些数满足\(a_i = i\)，因此原问题就等于让\(n-m\)个数的排列满足\(a_i \neq i\)的排列方案数
先说一个错误的做法：设\(dp_i\)表示长为\(i\)的排列的方案数。我们每次枚举一个大小为\(j\)的环，可以得到递推式子：
\[dp_i = \sum_{j=2}^{i}{ dp_{i-j} \times (j-1)! \times \binom{i}{j} } \]其中\((j-1)!\)为组成一个大小为\(j\)的环的方案数，\(\binom{i}{j}\)表示从\(i\)个排列中选\(j\)个，让他们组成环
我们发现这个是不对的，比如2 1 4 3，\(\binom{i}{j}\)会同时计算钦定环为2 1和4 3的情况，这很明显会重复。寄
正解做法：设\(dp_i\)表示长为\(i\)的排列的方案数。每次我们判断\(n\)这个数放在哪个位置：
-
放在不是\(n\)所在位置的位置，让后把这个位置删掉(因为他已经被填数了，而且这次填数没有任何环构成)
-
放在不是\(n\)所在位置的位置，并且这个位置的下标的数放在\(n\)这个位置(此时构成了一个环)
因此可以得出递推式：\(dp_i = (i-1) \times dp_{i-1} + (i-1) \times dp_{i-2}\)
思路总结：对于与环的个数有关的问题，递推式要考虑删掉环上一个没用的点或删掉一个大小为\(2\)的环的两种情况
\[\huge{\color{#ff0000}{\text{被xjk搏杀了，我tcl}}} \] 标签：排列,位置,times,计数,SDOI2016,binom,递推,P4071,dp From： https://www.cnblogs.com/fox-konata/p/17697665.html