CodeForces - 559C Gerald and Giant Chess（组合数，递推求阶乘逆元）

链接：CodeForces - 559C Gerald and Giant Chess

题意：

给出一个$h$行$w$列的棋盘（$1\le h,w\le 10^5$），其中有$n(1\le n\le 2000)$个点$(x_i,y_i)$不可走，每次只能往右或者往下走，问从左上角$(1,1)$到右下角$(h,w)$有多少条不同的路径。（结果对$1000000007$取余）

分析：

由于$n$只有$2000$，所以想到求出从左上到右下的所有路径数，然后减去从左上到右下经过这$n$个点的路径数。

①求$(x_1,y_1)$到$(x_2,y_2)$的路径数（$x_1\le x_2,y_1\le y_2$）

从$(x_1,y_1)$到$(x_2,y_2)$一共要走$(x_2?x_1)+(y_2?y_1)$步，要在其中选择$(x_2?x_1)$步是往下走的，那么一共有$C_{(x_2?x_1)+(y_2?y_1)}^{(x_2?x_1)}$种选法，即路径数

由于组合数
$$C_b^a=\frac{b!}{a!(b?a)!}$$

因此需要预先计算 $1$ ~ $2?10^5$的 阶乘 及其 阶乘的逆元

②递推求阶乘逆元

逆元可以看作原数的倒数，那么对于$n$的逆元则有：
$$\frac{1}{n!}=\frac{1}{(n+1)!}\times (n+1)$$

于是我们可以用 费马小定理+快速幂 或者 拓展欧几里得 求得最后一个数阶乘的逆元$finv[N]$，然后利用$finv[i]=finv[i+1]\times (i+1)\mathrm{m}\mathrm{o}\mathrm{d}p$从后往前推得所有数阶乘的逆元。

③从$(1,1)$开始经过$(x_i,y_i)$到达$(h,w)$的路径数

预处理得到以下变量：

• $d[i][0]$：从$(1,1)$到$(x_i,y_i)$的路径数
• $d[i][1]$：从$(x_i,y_i)$到$(h,w)$的路径数

所以 从$(1,1)$开始经过$(x_i,y_i)$到达$(h,w)$的路径数即为$d[i][0]?d[i][1]$

但是为了防止重复计算，应将点从左上到右下排序，从左上开始处理，计算完一个点后，应让 在其右下方的所有点的 $d[j][0]$ 减去 $d[i][0]?(x_i,y_i)到(x_j,y_j)的路径数$（即 减去从$(1,1)$开始经过$(x_i,y_i)$到达$(x_j,y_j)$的路径数）

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e3+50;
const LL N=2e5;
const LL MOD=1000000007;
LL f[N+5],finv[N+5];
LL qpow(LL a,LL b,LL c)
{
    LL res=1;while(b){
    if(b&1LL)res=(res*a)%c;a=(a*a)%c;b>>=1LL;}return res;
}
void init()
{
    f[0]=1;for(LL i=1;i<=N;i++)f[i]=(f[i-1]*i)%MOD;    //计算阶乘finv[N]=qpow(f[N],MOD-2,MOD);for(LL i=N-1;i>=0;i--)finv[i]=(finv[i+1]*(i+1))%MOD; //递推计算阶乘逆元
}
LL cal(LL x1,LL y1,LL x2,LL y2)   //计算(x1,y1)到(x2,y2)有多少条路径
{
    LL a=abs(x1-x2),b=abs(x1-x2)+abs(y1-y2);return (((f[b]*finv[a])%MOD)*finv[b-a])%MOD;
}
LL h,w;
LL d[maxn][2],ans;
int n;
struct point
{
    int x;int y;
}p[maxn];
bool cmp(point &a,point &b)
{
    if(a.x!=b.x)return a.x<b.x;elsereturn a.y<b.y;
}
int main()
{
    init();scanf("%lld %lld %d",&h,&w,&n);for(int i=1;i<=n;i++)scanf("%lld %lld",&p[i].x,&p[i].y);sort(p+1,p+n+1,cmp);for(int i=1;i<=n;i++){
    d[i][0]=cal(1,1,p[i].x,p[i].y);d[i][1]=cal(p[i].x,p[i].y,h,w);}ans=cal(1,1,h,w);   //总路径数for(int i=1;i<=n;i++){
    ans-=(d[i][0]*d[i][1])%MOD;if(ans<0)ans+=MOD;for(int j=i+1;j<=n;j++){
    if(p[j].y>=p[i].y)d[j][0]-=(d[i][0]*cal(p[i].x,p[i].y,p[j].x,p[j].y))%MOD;if(d[j][0]<0)d[j][0]+=MOD;}}printf("%lld\n",ans);return 0;
}