Luogu 2018 秋令营 Test 2

T1：

题目描述

Bob 来到了一个 $n imes m$ 的网格中，网格里有 $k$ 个豆子，第 $i$ 个豆子位于 $(x_i, y_i)$，保证没有两个豆子在同一个格子里，$(1, 1)$ 处和 $(n, m)$ 处没有豆子。

Bob 从左上角 $(1, 1)$ 出发，目的地是右下角 $(n, m)$。每次以向右或向下走一步，也就是说他到达终点时一共会走 $n + m - 2$ 步。

贪吃的 Bob 决定吃掉所有格子的豆子，他想知道是否存在多少条路径，使得他可以经过所有的豆子。由于答案很大，你只需要输出答案模 $10^9 + 7$ 的结果即可。

输入输出格式

输入格式：

第一行三个整数 $n, m, k$，意义如上所述。

接下来 $k$ 行，每行两个整数 $x_i, y_i(1 leq x_i leq n, 1 leq y_i leq m)$，意义如上所述。2018-10-14

输入输出样例

输入样例#1：

3 4 1
1 2

输出样例#1：

输入样例#2：

3 4 1
2 2

输出样例#2：

说明

对于 $30\%$ 的数据，满足 $2 leq n, m leq 100$。

对于 $60\%$ 的数据，满足 $2 leq n, m leq 1000$。

对于 $100\%$ 的数据，满足 $2 leq n, m leq 10^5, 0 leq k leq min(n imes m - 2, 10^5)$。

解题思路：

由于要吃掉所有的豆子且只能向右向下走，那么对于每一个豆子来说，如果在当前豆子的严格左下方处仍有豆子的话肯定无解，因为不可能向左走。

因此我们可以以每个豆子的X坐标作为第一关键字，Y坐标作为第二关键字对豆子进行排序。

接下来考虑如何计算方案：

可以想到方案是由乘法原理得到的，即每个当前点去往下一个点的方案数的总乘积。

对于60%的数据我们可以用dp[i][j]表示到由(1,1)到(i,j)的方案数，直接计算即可。

100%的数据：将dp[i][j]的表打出来可以发现是杨辉三角的变形，也就是组合数，由于数据范围较大考虑用乘法逆元计算组合数。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 100009
#define maxm 1009
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
    return x*f;
}
int n,m,k,tot;
struct node
{
    int x,y;
}p[maxn];
ll ans,base;

bool comp(node a,node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x; 
}


ll Quick_mul(ll a,ll b)
{
    ll sum=1;
    while(b)
    {
        if(b&1)
            sum=(sum*a)%base;
        a=(a*a)%base;
        b>>=1;
    }
    return sum%base;
}

ll inv(ll x)
{
    return Quick_mul(x,base-2)%base;
}

ll Cal(ll n,ll m)
{
    ll a=1,b=1;
    for(ll i=n-m+1;i<=n;i++)
        a=(a*i)%base;
    for(ll j=1;j<=m;j++)
        b=(b*j)%base;
    return a*inv(b)%base;
}

int main()
{
//    freopen("T1.in","r",stdin);
//    freopen("T1.out","w",stdout);
    n=read(),m=read(),k=read(),base=1e9+7;
    if(k>n+m-3)
    {
        puts("0");
        return 0;
    }
    p[0].x=1,p[0].y=1;
    for(int i=1;i<=k;i++)
        p[i].x=read(),p[i].y=read();
    sort(p+1,p+1+k,comp);        
    p[++k].x=n,p[k].y=m;
    ans=1;
    for(int i=1;i<=k;i++)
    {
        if(p[i].y<p[i-1].y)
        {
            puts("0");
            return 0;
        }
        ll x=(ll)p[i].x-p[i-1].x+1,y=(ll)p[i].y-p[i-1].y+1;
        ans=ans*Cal(x+y-2,y-1)%base; 
    }
    printf("%lld
",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code