interestingLSY 的博客

interestingLSY 的博客

震惊!处理连续一大串阶乘的逆元,竟然可以......

posted on 2018-08-11 08:19:03 | under 技巧 |

练习题:24OJ中"章鱼"一题

众所周知,直接处理一个数的逆元是 $O(logn)$ 的。

那么有没有 $O(n)$ 求出 $[1,n]$ 中所有数的阶乘的逆元的方法呢?

预备知识:逆元是完全积性函数:

即 $a^{-1} \times b^{-1} = (ab)^{-1}$

Solution I:

先用线性求逆元的方法求出 $[1,n]$ 中所有数的逆元

公式: $inv_i = (M-M/i)inv_{M\ mod\ i} \mod M$ (M为模数,且为质数)

然后用 $n!^{-1}=(n-1)!^{-1}\times n^{-1}$ 正着推一遍

Solution II:

$$\because a!^{-1} = a!^{-1} \times (a+1)^{-1} \times (a+1)$$

$$ = (a+1)!^{-1} \times (a+1)$$

先用费马小定理求出最大的阶乘的逆元,然后倒着推一遍就行啦!