LOJ 2034 – 「SDOI 2016」排列计数

题目链接:LOJ 2034

$n$个位置中恰好有$m$个位置是稳定的,即固定$m$个位置,此时有$n \choose m$种方案;对于剩下的$n – m$个位置,满足$A_i \neq i$,即是$n – m$的错位排列,有$d(n – m)$种。

根据分步计数原理,总共有${n \choose m} \cdot d(n – m)$种方案。

这里的错排方案函数$d(x)$很好处理,使用$d(x) = (x – 1) [d(x-1) + d(x-2)]$进行递推,当然这里要记得特殊处理$d(0) = 1$。在处理$n \choose m$的时候,我们可以先处理出$[1, \max \{ n \}]$内每个数字的阶乘,然后使用

$${n \choose m} = \frac{n!}{m!(n-m)!}$$

使用乘法逆元处理除法,由于这里的$p$为质数,$a$在模$p$意义下的乘法逆元等于$a^{p-2} \bmod p$。

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] LOJ 2034 – 「SDOI 2016」排列计数 […]