bzoj4517: [Sdoi2016]排列计数 组合数 DP 逆元

我们考虑一个DP F[i],表示F[i]个位置刚好错排的方案数。

然后我们考虑如何转移。f[0] = 1什么都不放

f[1] = 0 显然只有一个没法错排。

我们继续考虑,我们之前已经将{x,y……}放在一些其他位置,我们考虑我么当前i的摆放,如果i放在{x,y……}上的一个位置,那么以后就相当于求f[i – 1],如果我们放在一个还没放下的数的对应位置上,那么那个数日后无论如何都会错排,就相当于f[i – 2]。那么转移显然是f[i] = (i – 1) * (f[i – 2] + f[i – 1])。

据说这个东西叫错排公式,还有一个表示方法      D(n) = [n!/e+0.5]

那么我们只要再求出组合数就行了,但是case较多,最好On预处理出来。

我们考虑模数是p

p = k * i + r

k * i + r = 0 (mod p)

同乘 i^(-1) 和 r ^ (-1)

k * r^(-1) + i^(-1) = 0 (mod p)

i^(-1) = -k*r^(-1) (mod p)

i ^ (-1) =p – k * r ^ (-1) (mod p)

i ^ (-1) = p – (p / i)* (p % i) ^ (-1)

因为r = p%i,所以此时r的逆元已经求出。所以我们可以进行递推。

发表评论