试题分析

我们发现普通$dp$时间复杂度为$O(h \times w)$的，会$T$的很惨。而这个又无法通过优化，所以呢就要改变$dp$策略。

观察到$n\leq 2000$,所以我们需要设计出一个关于不能走的$dp$。

part1 排列组合应用

$C_i^j$的意思大家都知道把，但是这道题又与排列组合有什么关系呢。易证$C_{n+m}^n$的结果正好是从$(0,0)$走到$(n,m)$的方案数，通过插板法可证。

所以若我们从$(1,1)$出发，到终点$(n,m)$的方案数为$C_{n+m-2}^{n-1}$。

part2 dp

所以说$dp$式子就很好写了，$f(i)$表示只经过$i$号黑点的方案数，其余黑点均不参加。同时将最后所要求的$(h,w)$当作一个黑点。

则:$f(i)={C_{x_i+y_i-2}^{x_i-1}}-f(j)\times C_{x_i-x_j+y_i-y_j}^{x_i-x_j}  (j点在i点的左上角)。$

然后再用逆元求一下即可。

#include
      
       #include
       
        #include
        
         #include
         
          #define int long long#define mod 1000000007using namespace std;inline int read(){    int f=1,ans=0;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}    return f*ans;}const int N=200011;int inv[N],fac[N];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;}int n,m,k;struct node{    int x,y;}a[N];int C(int m,int n){
    if(n==0) return 1;return (fac[m]*((inv[n]*inv[m-n])%mod))%mod;}bool cmp(node x1,node x2){    if(x1.x==x2.x) return x1.y
          
           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;        }    }    printf("%lld",(f[k]%mod+2*mod)%mod);}