◆学时·V◆ 逆元法

□算法概述□

逆元运算是模运算中的一个技巧，一般用于解决模运算的除法问题。
模运算对于加、减、乘是有封闭性的，即 (a±b)%m=a%m±b%m，以及 (a×b)%m=a%m×b%m。但是对于除法运算不满足这样的规律。因此在处理两个大数相除的商模一个数会遇到困难。这时候需要逆元。
逆元的定义如下：

若 ab≡1 (mod m)，则对于模m，a、b互为逆元

那么就有 b≡a^-1。这就可以发挥作用了—— p/a%m=p*b%m，也就是除以一个数N再取模，等于乘上N的逆元再取模。

我们用 a^-1 表示a的逆元。

□逆元的计算□

一眼望过去全是数学……

费马小定理

当p为质数且a不为p的倍数时，满足 a^p-1≡1 (mod p)，所以有 a*a^p-2≡1，也就是说 a、a^p-2 互为逆元。

很简单是不是，但别忘了这只是p是质数的时候才能用！OI中经常会出现“答案模(1e9+7)”，很幸运，(1e9+7)就是一个很有用的质数！

算法I

其实许多算法没有想象的这么难……

对于模数m，一定有整数（一般定义是正整数）a、p、r 满足 m=pa+r ，可以看成“被除数=商*除数+余数”。

可以得到：ap+r≡0(mod m)→-ap≡r(mod m)→-pr^-1≡a^-1 ,也就是商与余数的逆元的积的相反数是除数的逆元。

当然大家都知道当 r=0 ，即 m被p整除时，r^-1是不成立的！

而这个算法最玄学的地方在与余数是一定小于除数的。这意味着什么呢？

—— 你在递推计算除数的逆元时，应该已经把余数的逆元算出来了。

算法II

不要慌……下面是一个递归式：

n^-1=(n-1)!·(n!)^-1

首先是一个不需要解释的小式子 n·[(n-1)!/n!]≡1。就很容易得到n的逆元就是(n-1)!/n!，稍微换一下，(n-1)!*(n!)^-1。

应该还有很多，一下子记不起来了 (｀・ω・´)

□除了做题好像没有什么用了□

传送门 ¦ARC 059 C¦
【翻译】

给出一个矩阵，在它的左下角剪去一个矩阵（只是一个角，保证剩余图形不是一个矩形），从左上角开始，可以向下或向右移动一个单位。

求从左上角到右下角的路径方案总数，答案模(1e9+7) （没错，就是这个不可描述的质数）

【解析】

很容易得到从A(p,q)到B(m,n)，则纵向移动 |n-q|，横向移动 |m-p| ，总共移动 |n-q|+|m-p| 。因此，如果我们把移动步骤表示为一个串，则一定有 |m-p| 个步骤是横向移动的。那么A到B的方案总数为 C(|m-p|,|m-p|+|n-q|)。

假设现在没有剪去角，则矩形(r,c)从左上到右下方案总数为 C(r+c,r) = A。

我们还可以算出从剪去矩阵内的点出发，到达右下角的方案数B，由于答案与这些方案是补集，所以全集A减去子集B就是答案了。

但是计算组合数时就遇到了困难，此时就需要逆元。可以用初始化直接解决，当然需要使用快速幂。（计算逆元的函数是Pre，快速幂函数是PowMod）

【源代码】

/*Lucky_Glass*/

#include<cstdio>

#include<algorithm>

using namespace std;

#define MO 1000000007

#define MAXN 200005

#define LL long long

LL inv[MAXN],s[MAXN];

int n;

LL PowMod(LL a,int b)

{

    LL ret=;

    while(b)

    {

        if(b&) ret=ret*a%MO;

        a=a*a%MO;

        b>>=;

    }

    return ret;

}

void Pre()

{

    s[]=;

    for(int i=; i<=n; i++)

        s[i]=s[i-]*i%MO;

    inv[]=;

    inv[n]=PowMod(s[n],MO-);

    for(int i=n-; i>; i--)

        inv[i]=inv[i+]*(i+)%MO;

}

LL C(int a,int b){if(a<||b<) return ;return s[a]*inv[b]%MO*inv[a-b]%MO;}

int main()

{

    int h,w,A,B;

    scanf("%d%d%d%d",&h,&w,&A,&B);

    n=h+w-;

    Pre();

    LL ans=C(h+w-,h-);

    for(int i=; i<=B; i++)

    {

        ans-=C(h-A+i-,h-A-)*C(A-+w-i,A-)%MO;

        ans=(ans%MO+MO)%MO;

    }

    printf("%lld\n",ans);

}

The End

Thanks for reading!

- Lucky_Glass

巴特西

【学时总结】◆学时·V◆ 逆元法