51nod 1486 大大走格子（dp，容斥）

參考題解：http://blog.csdn.net/mrazer/article/details/52047436

看到題首先是要想到容斥，因為之前看的一篇容斥的文章講到過。不過裡面把這部分内容劃掉了，因為講的有問題。。。。其次呢，想到機器人走方格的題目，畢竟這隻是比那個多了個不能走的格子，不過想了想，還是不會做啊

還是好好看題解吧。。。

我把題解中的狀态轉移方程展開了幾項，正好是++–的容斥形式。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = +;
const int MAXN = +;
const int MAXP = ;
struct Point
{
    int x,y;
} p[MAXP];
LL fac[MAXN*];
LL inv[MAXN*];
LL res[MAXP];
int h,w,n;

template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF) return ; //EOF
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-:;
    ret=(c=='-')?:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*+(c-'0');
    ret*=sgn;
    return ;
}
inline void out(LL x)
{
    if(x>) out(x/);
    putchar(x%+'0');
}

void println(LL num)
{
    out(num);
    puts("");
}

LL mpow(LL a,LL b)
{
    LL ret = ;
    while(b)
    {
        if(b&) ret = ret*a%mod;
        a = a*a%mod;
        b >>= ;
    }
    return ret;
}

LL calc(LL n, LL m)
{
    n = n+m;
    LL ret = (fac[n]*inv[m]%mod)*inv[n-m]%mod;
    return ret;
}

bool cmp(const Point& a, const Point& b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    scan_d(h);
    scan_d(w);
    scan_d(n);
    for(int i = ; i < n; ++i)
    {
        scan_d(p[i].x);
        scan_d(p[i].y);
    }
    fac[] = inv[] = ;
    for(int i = ; i <= h+w; ++i)
    {
        fac[i] = fac[i-]*(LL)i%mod;
        inv[i] = mpow(fac[i],mod-);
    }
    p[n].x = h,p[n].y = w;
    sort(p,p+n,cmp);

    for(int i = ; i <= n; ++i)
    {
        res[i] = calc(p[i].x-,p[i].y-);
        for(int j = ; j < i; ++j)
        {
            if(p[i].x >= p[j].x && p[i].y >= p[j].y)
            {
                res[i] = ((res[i]-res[j]*calc(p[i].x-p[j].x,p[i].y-p[j].y)%mod)%mod+mod)%mod;
            }
        }
    }
    println(res[n]);
    return ;
}