题目描述

给定一个 H*W 的棋盘，棋盘上只有 N 个格子是黑色的，其他格子都是白色的。

在棋盘左上角有一个卒，每一步可以向右或向下移动一格，并且不能移动到黑色格子中。

求这个卒从左上角移动到右下角，一共有多少种路线。

输入格式
第一行包含三个整数H,W,N。

接下来N行，每行包含两个整数x，y，描述一个黑色格子位于x行y列。

数据保证左上角和右下角的格子都是白色的。

输出格式
输出一个整数表示结果对$10^9+7$取模后的值。

数据范围
$1 \le H,W \le 10^5$
$1 \le N \le 2000$

输入样例1：

3 4 2 
2 2 
2 3

输出样例1：

2

输入样例2：

100 100 3
15 16
16 15
99 88

输出样例2：

545732279

解题报告

题意理解

一个$H \times W$的方格,现在你要从$(1,1)$走到$(n,m)$,每一次可以往下走,或者往右边走,同时有些格子是禁忌格子,也就是你不可以走到那里去,现在要你统计,有多少个合法方案.
Hint:合法方案数要对$10^9+7$取模

算法选择

一道棋盘问题,不是搜索,就是动态规划,一般来说这种棋盘,往往就是这个套路.而这道题目显然根据合法方案数,和那个超大取模数,就可以让我们确定这道题目是计数类动态规划.

思路详解

计数类型的动态规划,不同于其他问题,它具有一个非常显著的特性,就是不能重叠,不能遗漏.这也决定了,计数类型的动态规划算法,与其他动态规划算法的一个区别,就是它和组合数学紧密相连.

一个题目的答案目标,决定着题目的性质.
最值问题:单调性or重叠性(不漏可重)
方案数问题:组合数学性or完美匹配集合性质(不重不漏).

(以上性质,请形象理解,毕竟都不是专业术语,而是笔者自己刷题的感悟)

这道题目既然最终的目标让我们求解方案数,那么显然我们就要明确一点,我们必须不重不漏.

而且这道题目,既然是和组合数学有关,那么我们不得不想到,这道题目的前世,也就是著名的一大棋盘模型.

从$(1,1)$走到$(n,n)$的方案数,为$C_{2 \times n}^{n}$.

因为我们从$(1,1)$走到$(n,n)$,那么显然我肯定是要走$n$步向右走,$n$步向左走,那么此时我们就可以认为,一组合法的方案就是,由一组01串构成,其中$0$表示向右走,$1$表示向下走,而且$0$和$1$的个数都是$n$个.

而我们本题和上面的经典模型相比,只有一点不同,那就是我们这道题目,它存在禁忌格子,我们不可以抵达那个格子.

综上所述,我们发现按照原题的合法方案数,其实就是所有的方案数-不合法的方案数.

即合法方案数=所有的方案数-不合法的方案数.

看到这一点,我们立即就会想到,这道题目是不是要用到容斥原理.

因此这道题目的算法就是.组合数求法(费马小定理+逆元)+容斥原理+动态规划=本题计数型动态规划.

具体算法都想到了,那么接下来就是最为精妙,也最为重要的一步,状态设计,决策转移.

因为对于一道动态规划题目而言,状态设计,既是第一步,也是仅次于决策转移的重要一步.

计算合法方案非常困难,那么我们不如计算不合法的方案数.这就是容斥原理最为核心的一个点,那就是反向思维,抛去难点,算容易点.

我们会发现禁忌(黑色)格子的数量最多也就$2000$个,相比于白色格子最多的$10^10$,我们不用说,状态的设计,肯定得和黑色禁忌格子有关联

一个方案里面只要有黑色禁忌格子,那么绝对就是不合法的方案,所以说我们不妨,通过总方案减去不合法方案,来达到计算我们最终的合法方案数.

首先呢,我们可以将所有的黑色格子排序,排序的准则,就是行列坐标递增.而且我们可以认为,左上角是第0个黑色格子,右下角是$N+1$个黑色格子.

那么我们就可以设第$i$个黑色格子的横纵坐标为$(X_i,Y_i)$,那么$F[i]$表示为从左上角走到第$i$个黑色格子,而且途中不经过其他黑色格子的方案数

因此我们可以找出公式
$$F[i]=C_{x_i-1+y_i-1}^{x_i-1}-\sum_{j=0}^{i-1}{F[j]*C_{x_i-x_j+y_i-y_j}^{x_i-x_j}}$$
其中$x_i \le x_j,y_i \le y_j$

一个数学公式,总是让人崩溃,那么我们不如将其转换成为中文理解.

$F[i]=(1,1)到(x_i,x_j)的总方案数-前i-1黑格方案数*黑格到(x_i,y_i)的方案数$

然后这道题目的最终答案,显然就是我们的$F[n+1]$

然后一个重点就是,我们要预先预处理关于$10^9+7$的乘法逆元来计算.

代码解析

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=200010;
const int Mod=1e9+7;
int n,m,k;
long long f[N],jc[N],jcinv[N];
pair<int,int> date[N];
long long ksm(long long a,long long b,long long c)
{
    long long ans=1%c;
    while(b)
    {
        if (b&1)
            ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans;
}
long long C(int n,int m)
{
    return (long long)jc[n]*jcinv[m]%Mod*jcinv[n-m]%Mod;
}
void init()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
        cin>>date[i].first>>date[i].second;
    jc[0]=jcinv[0]=1;
    for(int i=1;i<N;i++)
    {
        jc[i]=jc[i-1]*(long long)i%Mod;
        jcinv[i]=jcinv[i-1]*(long long)ksm(i,Mod-2,Mod)%Mod;
    }
    sort(date+1,date+1+k);
    date[k+1]=make_pair(n,m);
    f[0]=1;
    return ;
}
void work()
{
    for(int i=1;i<=k+1;i++)
    {
        int x=date[i].first,y=date[i].second;
        f[i]=C(x+y-2,x-1);
        for(int j=1;j<i;j++)
        {
            int a=date[j].first,b=date[j].second;
            if (a<=x && b<=y)
                f[i]=(f[i]-f[j]*(long long)C(x-a+y-b,x-a))%Mod;
        }
    }
}
void out()
{
    cout<<(f[k+1]+Mod)%Mod<<endl;
    return ;
}
signed main()
{
    init();
    work();
    out();
    return 0;
}