CodeForces559C Gerald and Giant Chess

题意:一个h*w的格子，里面有m个障碍物,问从1,1走到h,w的路径有有多少条(h,w<1e5, m<2000)

题解:首先要知道这个题的简化版，也就是说没有障碍物，方案数为c(n+m, n)，现在添加了障碍物，可以想到用容斥来去重，但是m<2000直接容斥不可行，考虑容斥的时候有重复计算过程中集合之间有一定关系，每一个点，设f[i] 为从出发点不经历一个黑点的答案，那么可以n^2进行更新，注意预处理

#include <bits/stdc++.h>
#define maxn 201000
#define INF 0x3f3f3f3f
#define fi first
#define se second
typedef long long ll;
using namespace std;
const ll mod = 1e9+7;
pair<ll ,ll >p[maxn];
ll dp[maxn], inv[maxn], fac[maxn];
ll exp_mod(ll a,ll b,ll p){
    ll ans = 1;
    a %= p;
    while(b){
        if(b&1) ans = ans*a%p;
        a = (a*a)%p;
        b >>= 1;
    }
    return ans;
}
ll cal(ll n,ll m){
    return fac[n+m]*inv[n]%mod*inv[m]%mod;
}
int main(){
    ll h, w, n;
    scanf("%lld%lld%lld", &h, &w, &n);
    for(ll i=0;i<n;i++) scanf("%lld%lld", &p[i].fi, &p[i].se);
    p[n] = make_pair(h, w);
    sort(p, p+n+1);
    dp[0] = fac[0] = inv[0] = 1;
    for(int i=1;i<=2e5;i++){
        fac[i] = fac[i-1]*i%mod;
        inv[i] = exp_mod(fac[i], mod-2, mod);
    }
    for(ll i=0;i<=n;i++){
        dp[i] = cal(p[i].fi-1, p[i].se-1);
        for(ll j=0;j<i;j++){
            if(p[i].fi>=p[j].fi&&p[i].se>=p[j].se)
                dp[i] = (dp[i]-dp[j]*cal(p[i].fi-p[j].fi, p[i].se-p[j].se)%mod)%mod;
        }
    }
    printf("%lld
", (dp[n]+mod)%mod);
    return 0;
}