[CF559 C]Gerald and Giant Chess

迷南。 2023-08-17 17:38 130阅读 0赞

#### 题面描述 ####

给定一个\\(H\*W\\)的棋盘，棋盘上只有\\(N\\)个格子是黑色的，其他格子都是白色的。在棋盘左上角有一个卒，每一步可以向右或者向下移动一格，并且不能移动到黑色格子中。求这个卒从左上角移动到右下角，一共有多少种可能的路线。

#### 输入格式 ####

第\\(1\\)行：\\(3\\)个正整数\\(h,w,n(1 \\leq h,w \\leq 10^5,1\\leq n \\leq 2000)\\)。  
接下来n行，第\\(i+1\\)行包含两个整数\\(r\_i,c\_i\\)，即黑色格子的坐标

#### 输出格式 ####

输出一个整数，即总的方案数。

#### 样例 ####

##### 样例输入 #####

100 100 3  
15 16  
16 15  
99 88

##### 样例输出 #####

545732279

#### 题解 ####

题目的数据范围肯定是不能直接写暴力的(即使是记忆化搜索也会导致空间超限)。因此我们考虑先用组合计数的方式求出总的方案数，再减去不合法的方案数。  
在一个正方形矩阵中，我们若想用最小的步数从\\((0,0)\\)走到\\((x,y)\\)，一共只需要走x+y步，而决定方案数的仅仅是我们选择第\\(i\\)步是向\\(x\\)坐标移动还是向\\(y\\)坐标移动，因此可知总方案数为\\(C\_\{x+y\}^\{x\}\\)  
我们再减去其中加上所有会到达黑色方块的方案数即可。

#include<bits/stdc++.h>
    #define int long long
    #define mod 1000000007
    #define maxn 200011
    using namespace std;
    inline char get(){
        static char buf[30000],*p1=buf,*p2=buf;
        return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
    }
    inline int read(){
        register char c=get();register int f=1,_=0;
        while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
        while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
        return _*f;
    }
    struct edge{
        int x,y;
    }a[maxn];
    bool cmp(edge x1,edge x2){
        if(x1.x==x2.x) return x1.y<x2.y;
        return x1.x<x2.x;
    }
    int inv[maxn],fac[maxn];
    int ksm(int a,int b){
        int ans=1;
        while(b){
            if(b&1) ans*=a,ans%=mod;
            a*=a,a%=mod;
            b>>=1;
        }return ans%mod;
    }
    inline void init(){
        inv[0]=1,fac[0]=1;
        for(register int i=1;i<maxn;i++){
            fac[i]=(fac[i-1]*i)%mod;
            inv[i]=ksm(fac[i],mod-2);
        }
    }
    int n,m,k;
    int C(int m,int n){
        if(n==0)return 1;
        return (fac[m]*((inv[n]*inv[m-n])%mod))%mod;
    }
    int f[maxn];
    signed main(){
        //freopen("1.txt","r",stdin);
        init();
        n=read(),m=read(),k=read();
        for(register int i=1;i<=k;i++)a[i].x=read(),a[i].y=read();
        sort(a+1,a+k+1,cmp);
        k++;
        a[k].x=n,a[k].y=m;
        for(register int i=1;i<=k;i++){
            f[i]=C(a[i].x+a[i].y-2,a[i].x-1)%mod;
            for(register int j=1;j<i;j++){
                if(a[j].x>a[i].x||a[j].y>a[i].y) continue;
                f[i]-=f[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x);
                f[i]=((f[i]%mod)+mod)%mod;
            }
        }
        cout<<(f[k]%mod+mod)%mod;
    }

转载于:https://www.cnblogs.com/Chen574118090/p/11608903.html