51nod 1486 大大走格子——容斥

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1486

已知起点到某个障碍点左上角的所有点的不经过障碍的方案数，枚举哪个障碍点是第一个碰到的障碍点，即可枚举到所有非法状态。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=,M=(N*N>>),mod=1e9+,K=1e5+;

int n,m,k,hd[N],xnt,to[M],nxt[M],ans[N],jc[K<<],jcn[K],mxx,mxy;

struct Node{

    int x,y;

}a[N];

bool cmp(Node u,Node v)

{

    return u.x==v.x?u.y<v.y:u.x<v.x;

}

void add(int x,int y)

{

    to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;

}

int pw(int x,int k)

{

    int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;

}

void init()

{

    int mx=max(n,m),he=n+m;

    jc[]=;

    for(int i=;i<=he;i++) jc[i]=(ll)jc[i-]*i%mod;

    jcn[mx]=pw(jc[mx],mod-);

    for(int i=mx-;i>=;i--) jcn[i]=(ll)jcn[i+]*(i+)%mod;

}

int C(int n,int m)

{

    return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    init();

    for(int i=;i<=k;i++)

    {

        scanf("%d%d",&a[i].x,&a[i].y);

        a[i].x--;a[i].y--;

    }

    a[++k].x=n-; a[k].y=m-;

    sort(a+,a+k+,cmp);

    for(int i=;i<=k;i++)

    {

        ans[i]=C(a[i].x+a[i].y,a[i].x);

        for(int j=;j<i;j++)

            if(a[j].x<=a[i].x&&a[j].y<=a[i].y) add(i,j);

    }

    for(int i=;i<=k;i++)

        for(int j=hd[i],v=to[j];j;j=nxt[j],v=to[j])

            ans[i]=(ans[i]-(ll)ans[v]

                *C(a[i].x-a[v].x+a[i].y-a[v].y,a[i].x-a[v].x)%mod+mod)%mod;

    printf("%d\n",ans[k]);

    return ;

}