求逆元

相关定理

1. 费马小定理，有$n^{p-1}\equiv 1(\mathrm{mod}p)$。 因此$\frac{1}{n}\equiv n^{p-2}(\mathrm{mod}p)$

2. 方程$ax\equiv 1(\mathrm{mod}p)$的解被称为a关于模p的逆元。当p为素数且$gcd(a,p)=1$（此时必有解且唯一）时，由费马小定理可得$x\equiv a^{p-2}(\mathrm{mod}p)$。

   例如: $x=\frac{5}{2}modp$可以转化为$x=5\ast 2^{p-2}\mathrm{\%}p$

求逆元方法:

通过扩展欧几里得算法求逆元

// when we used this method to calculate x / y % p, we also need x and p is coprime 
// Method 1: 	Extended Euclid
// Requires:	a and b is coprime
// Modify:  	x, y
// Effects: 	when the method is finished, x is a's inverse element about b.
// Return:  	gcd(a, b)

int ex_gcd(int a, int b, int &x, int &y) {
	int ret, tmp;
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	ret = ex_gcd(b, a % b, x, y);
	tmp = x;
	x = y;
	y = tmp - a / b * y;
	return ret;
}

通过递推求1~n的逆元

$$inv[i]=(p-\frac{p}{i})\ast inv[p\mathrm{\%}i]\mathrm{\%}p$$

这个算法可以在$O(n)$的时间复杂度内求出n以内所有数的逆元，不过需要注意的是p必须为奇质数。

// when we used this method to calculate x / y % p, we also need x and p is coprime
// Method 3:	Recursive to get i's inverse element
// Requires:	p is prime and p != 2
// Modify:  	inv[]
// Effects: 	inv[i] is i's inverse element about p;

int inv[N];
void get_inverse(int n, int p) {
	inv[1] = 1;
	for (int i = 2; i <= n; ++i) {
		inv[i] = (p - p / i) * inv[p % i] % p;
	}
}

阶乘的逆元:

$$invf[i]=invf[i+1]\ast (i+1)\mathrm{\%}p$$

// when we used this method to calculate x / y % p, we also need x and p is coprime
// Method 4:	Recursive to get Factorial[i] and their inverse element
// Requires:	p is prime
// Modify:  	invf[], factor[]
// Effects:  	factor[i] is i's factorial, invf[i] is factor[i]'s inverse element

int invf[N], factor[N];
void get_factorial_inverse(int n, int p) {
	factor[0] = 1;
	for (int i = 1; i <= n; ++i) {
		factor[i] = i * factor[i - 1] % p;
	}
	invf[n] = quick_inverse(factor[n], p);
	for (int i = n-1; i >= 0; --i) {
		invf[i] = invf[i + 1] * (i + 1) % p;
	}
}

HDU5698 瞬间移动(求逆元)

我们要从$(1,1)$点走到$(n,m)$点，只能向右下角的格子里走，那么$(1,1)$所在的行和列不能走,$(n,m)$所在的行和列不能走，那么能走的面积就是$(n-2)\ast (m-2)$这么大的面积，行和列分别考虑，实质上就是求组合数$C_{(n-2)+(m-2)}^{n-2}$

因为$C_n^m=\frac{n!}{m!\ast (n-m)!}$,乘以一个数等于乘这个数的逆元，我们先预处理出阶乘的逆元。

首先求出一个数模p的逆元:

$$f[i]=(p-\frac{p}{i})\ast f[p\mathrm{\%}i]\mathrm{\%}p$$

然后再递推出$n!$的逆元

$$inv[(n-1)!]=inv[n!]\ast n\mathrm{\%}p$$

可以得到

$$inv[n!]=inv[(n-1)!]\ast f[n]\mathrm{\%}p$$

然后就可以求出组合数了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=200000+20;
ll fac[N]= {1,1},inv[N]= {1,1},f[N]= {1,1};
/*
fac[i]:i的阶乘
inv[i]:i的阶乘的逆元
f[i]:i的逆元
*/
ll C(ll a,ll b)//除以一个数等于乘这个数的逆元
{
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
void init()
{
    for(ll i=2; i<N; i++)
    {
        fac[i]=fac[i-1]*i%mod;
        f[i]=(mod-mod/i)*f[mod%i]%mod;
        inv[i]=inv[i-1]*f[i]%mod;
    }
}

int main()
{
    ll n,m;
    init();
    while(cin>>n>>m)
        cout<<C(m+n-4,m-2)<<endl;
    return 0;
}