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 ;
}