线性求阶乘逆元

· · 个人记录

阿巴阿巴。

今天考试T1是这个玩意。

这是题解。

很明显这不是我考试时能想出来的东西...

然后这题要用到阶乘的逆元，但显然逆元数组开不到1e9+7这么大。

所以就用这道来总结一下线性求阶乘逆元。

按照惯例，我应该先来一句激励自己的惊世骇俗的好词佳句

但想不出来了所以咕了

首先我们先来预习复习一下线性求逆元：

inv[i]=(p-p/i) \times \;inv[p \; mod \; i]\; mod \;p

其中 p 为质数，i 在 for (int \;i=1;i<=n;i++) 中枚举。

好了，现在你已经会线性求逆元了。

但是知周所，在组合数学之中逆元总是伴着阶乘出现的，而常常我们没办法把数组开到那么大，又不想一个一个求逆元。

那么便有了一个不知道谁发明的线性求阶乘逆元的方法。

当然，前提是p必须要是质数(因为要用到费马小定理来求最大的阶乘逆元)。

然后下面是柿子：


    for (int i = m + n - 1; i >= 0; i--) {
        inv[i] = ((inv[i + 1] % p) * ((i + 1) % p)) % p;
    }

其中最大的阶乘逆元 inv[m+n] 需要用费马小定理求出。

柿子的原理很简单，如下：

1.首先用费马小定理求出最大的阶乘逆元，即求出 mod \; p 意义下(n+m)!^{p-2}。

2.用for循环倒序枚举，转换成已知\frac{1}{(i+1)!} 求\frac{1}{i!}。

很明显只需要乘以(i+1) 就可以了。

所以，没了。

AC code。

值得一提的是，建议点那个显示原始代码阿巴