【AT_dp_y】Grid 2 - Harvey

题意

要求从 \((1,1)\) 走到 \((n,m)\)，不能经过障碍物，问方案数。
\(1 \leq n,m \leq 10^5,1 \leq k \leq 3000\)。

思路

首先先解决弱化版，若没有障碍物的方案数，显然是 \(\binom{n+m-2}{n-1}\)。
则我们可以用总 - 非法，考虑经过多少个障碍物进行容斥。
如果按个数去枚举障碍物以容斥，必定会超时，那怎么办呢？
先把障碍物按 \(x,y\) 升序排列。
考虑用 \(dp\)，设计 \(f_{i,j}\) 表示当前在 \(i\) 号障碍物，之前一共经过 \(j\) 个障碍物的方案数。
转移显然。
但是是 \(O(n^2)\) 级别的，再次优化状态。
发现 \(j\) 是不重要的，他只是决定在容斥中这个状态是加还是减。
所以可以变成 \(f_{i,0/1}\)。
本题用到了 \(3\) 种方法：

1. 用总 - 非法
2. 对于难以容斥的考虑 \(dp\)
3. 在容斥 \(dp\) 中，个数往往是不重要的，可以用 \(0/1\) 表示。

code

#include<bits/stdc++.h>
#define ll long longusing namespace std;const ll N = 2e3+5,M = 1e5+5,mod = 1e9+7;struct node{ll x,y;
}a[N];
ll n,m,k;
ll ans;
ll fac[M<<1];
ll f[N][2];ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}bool cmp(node x,node y){return (x.x==y.x ? x.y<y.y : x.x<y.x);
}
ll C(ll x,ll y){return fac[x]*qpow(fac[y],mod-2)%mod*qpow(fac[x-y],mod-2)%mod;
}
void add(ll &x,ll y){(x+=y)%=mod;
}
int main() {cin>>n>>m>>k;for(int i=1;i<=k;i++)cin>>a[i].x>>a[i].y;fac[0]=1;for(int i=1;i<=n+m;i++)fac[i]=fac[i-1]*i%mod;sort(a+1,a+k+1,cmp);ans=C(n+m-2,n-1);for(int i=1;i<=k;i++)f[i][1]=C(a[i].x+a[i].y-2,a[i].x-1);for(int i=1;i<=k;i++){for(int j=1;j<i;j++){if(a[i].x>=a[j].x && a[i].y>=a[j].y){for(int t=0;t<=1;t++){add(f[i][t],f[j][t^1]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)%mod);}}}}for(int i=1;i<=k;i++){ll val=C(n+m-a[i].x-a[i].y,n-a[i].x);ans-=f[i][1]*val%mod,ans=(ans+mod)%mod;ans+=f[i][0]*val%mod,ans%=mod;}cout<<ans;return 0;
}