Codeforces 559C Gerald and Giant Chess 組合數學 DP

題目大意：

就是現在對于一個H*W的棋盤從點(1, 1)走到(H, W), 每次隻能x++或者y++地走, 其中棋盤上有n個點是壞點, 也就是不能走的點, 那麼從(1, 1)到(H, W)不經過這n個壞點的路徑有多少種, H, W <= 100000, n <= 2000

大緻思路：

首先在不考慮壞點的情況下, 從(x1, y1)走到(x2, y2), x2 >= x1, y2 >= y1一共有C(x2 - x1 + y2 - y1, x2 - x1)種方案

那麼考慮壞點的情況要去除掉

先将所有壞點坐标按照x第一關鍵字, y第二關鍵字排序

用dp[i]表示目前從起點到達第i個壞點沒有經過任何其他壞點的路徑數

那麼對于第i個壞點 dp[i] = C(xi - 1 + yi - 1, xi - 1) - sigma(dp[j]*C(xi - xj + yi - yj, xi - xj))

其中j < i且滿足xj <= xi, yj <= yi, 由于dp[j]表示的是直到到達j點前面都沒有經過壞點的路徑, 對于j < i的所有j, dp[k]*C(xi - xj + yi - yj, xi - xj)表示的路徑之間是沒有重複的

于是時間複雜度為O(nlogn + n*n), 注意組合數可以預處理階乘, 當然由于這題時限卡的不是很緊, 不用預處理階乘的逆元, 每次直接求逆元也可以過....

代碼如下：

Result  :  Accepted     Memory  :  1608 KB     Time  :  1170 ms

/*
 * Author: Gatevin
 * Created Time:  2015/8/14 12:49:15
 * File Name: Sakura_Chiyo.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

const lint mod = 1e9 + 7;

struct point
{
    int x, y;
    point(){}
};

bool cmp(point p1, point p2)
{
    return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}

point p[2020];
int H, W, n;
lint dp[2020];
lint fac[200010];

lint quick(lint base, lint pow)
{
    lint ret = 1;
    while(pow)
    {
        if(pow & 1) ret = ret*base % mod;
        pow >>= 1;
        base = base*base % mod;
    }
    return ret;
}

lint C(lint x, lint y)
{
    return fac[x]*quick(fac[y]*fac[x - y] % mod, mod - 2) % mod;
}

int main()
{
    fac[0] = 1;
    for(int i = 1; i < 200010; i++)
        fac[i] = fac[i - 1]*i % mod;
    scanf("%d %d %d", &H, &W, &n);
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    p[0].x = p[0].y = 1;
    p[n + 1].x = H, p[n + 1].y = W;
    sort(p, p + n + 2, cmp);
    dp[0] = 1;
    for(int i = 1; i <= n + 1; i++)
    {
        dp[i] = C(p[i].x - p[0].x + p[i].y - p[0].y, p[i].x - p[0].x);
        for(int j = 1; j < i; j++)
            if(p[j].y <= p[i].y)
                dp[i] = (dp[i] - dp[j]*C(p[i].x - p[j].x + p[i].y - p[j].y, p[i].x - p[j].x) % mod + mod) % mod;
    }
    printf("%I64d\n", dp[n + 1]);
    return 0;
}