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

练习题: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)$$ 先用费马小定理求出最大的阶乘的逆元，然后倒着推一遍就行啦！