cf559 C. Gerald and Giant Chess（dp+组合数）

题意：

n*m网格，其中有k个网格中有障碍物不能走。每步只能往下或往右求从左上走到右下的路径数。

\(1\le n,m\le 1e5,1\le k \le 2000\)

思路：

网格总数很大，但是障碍物很少，显然复杂度跟障碍数有关。

一开始想的是容斥：所有路径数 - 经过至少一个障碍的路径数 + 经过至少两个障碍的路径数 - …… ，然后就晕了

正解：对所有障碍物排序，\(dp(i)\) 表示从左上走到第 \(i\) 个障碍物，中间不经过任何一个障碍物的路径数

怎么计算 \(dp(i)\) 呢？可以把从左上走到第 \(i\) 个障碍物的路径这样分类：不经过任何一个障碍物的、路径上第一个障碍物的序号为1、路径上的第一个障碍物为2、……

那么 \(dp(i)=C_{x_i-1+y_i-1}^{x_i-1}-\sum\limits _{会影响到i的j} dp(j)*C_{x_i-x_j+y_i-y_j}^{x_i-x_j}\)

为方便，增加一个位于终点的障碍物。

ll del(ll x, ll y) { return x-y<0?x-y+MOD:x-y; }

main()
{
    iofast;
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i++) cin >> a[i].fi >> a[i].se;

    init(); //预处理阶乘和逆元
    sort(a + 1, a + 1 + k);
    a[++k] = {n,m};

    for(int i = 1; i <= k; i++)
    {
        ll x = a[i].fi, y = a[i].se;
        for(int j = 1; j < i; j++)
            if(a[j].fi <= x && a[j].se <= y)
                (dp[i] += dp[j] * C(x-a[j].fi+y-a[j].se,x-a[j].fi) % MOD) %= MOD;
        dp[i] = del( C(x-1+y-1,x-1) , dp[i]);
    }
    cout << dp[k];
}