问题描述:

给你一个$h*w$的网格,其中有$n$个黑色的格子,它们的位置为$(x_i, y_i)$。你从左上角开始,每一步只能向左或者下移动,并且不能经过黑色格子,问你有多少种到达右下角的方案。

输入:

第一行给你三个数$h, w, n$($1<=h, n<=10^5, 1<=n<=200$)

输出:

输出对$10^9+7$取模的方案数

思路:

感觉JXOI很喜欢考计数类DP,然而自己菜的一比。。。

首先我们就是要考虑如何设计一个状态,能够统计DP时的信息,并且能够根据这个状态不重不漏地进行DP(我觉得计数类DP就是这个难,状态转移反而容易一些)。因为黑色格子不多,所以我们的复杂度应该和黑色的格子有关。我们可以先将黑色格子按照横纵坐标排序,然后设$f[i]$为到达$i$个黑色格子且不经过前$i-1$个黑色格子的可能路径数。特别的,设$f[n+1]$的坐标为$(h+1, w+1)$,那么答案就是$f[n+1]$了。

接下来我们考虑如何计算和转移。我们可以先计算出到达第$i$个黑色格子所有路径,这个的数量为$C_{x_i+y_i-2}^{x_i-1}$,原因是一共要向下或向左走$x_i+y_i-2$步,然后其中要任选$x_i-1$步向左走。然后还要减去经过前面黑色格子的路径数,因此我们可以推出DP方程为:$$f[i]=C_{x-i+y_i-2}^{x_i-1}-\sum_{j=0}^{i-1} f[j]*C_{x_i+y_i-x_j-y_j}^{x_i-x_j}$$
还要特别注意的是如果$x_j>x_i$或者$y_j>y_i$时,这一项是不用减去的。

代码:

#include <bits/stdc++.h>
#define MAXN 300005
#define p 1000000007
#define LL long long
using namespace std;

int h, w, n;
LL f[MAXN], fac[MAXN], inv[MAXN];

struct Node {int x, y;} a[MAXN];

bool CMP(Node x, Node y)
{
    if(x.x==y.x) return x.y<y.y;
    else return x.x<y.x;
}

LL comb(LL n, LL m)
{
    return fac[n]*inv[n-m]%p*inv[m]%p;
}

void init()
{
    inv[0]=fac[0]=fac[1]=inv[1]=1;
    for(int i=2; i<=MAXN-5; i++)
    {
        fac[i]=(fac[i-1]*i)%p;
        inv[i]=inv[p%i]*(p-p/i)%p;
    }
    for(int i=2; i<=MAXN-5; i++) inv[i]=(inv[i]*inv[i-1])%p;
}

int main()
{
    init();
    scanf("%d%d%d", &h, &w, &n);
    for(int i=1; i<=n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a+1, a+n+1, CMP);
    a[n+1].x=h; a[n+1].y=w;
    for(int i=1; i<=n+1; i++)
    {
        f[i]=comb(a[i].x+a[i].y-2, a[i].x-1);
        for(int j=1; j<i; j++)
        {
            if(a[j].x>a[i].x || a[j].y>a[i].y) continue;
            f[i]=(f[i]-f[j]*comb(a[i].x+a[i].y-a[j].x-a[j].y, a[i].x-a[j].x))%p;
        }
    }
    printf("%lld\n", (f[n+1]+p)%p);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注