UVALive 6916---Punching Robot(卢卡斯+容斥)

题目链接

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4928

与HDU 5794相似 博客链接

题意：在一个棋盘状的网格中，有很多障碍点，求从（1，1）走到（n，m）的方法数？

思路：对障碍点进行排序，两重循环去重，加上卢卡斯定理快速求组合数；

代码如下：

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <string.h>

#include <cmath>

using namespace std;

const long long mod=;

typedef long long LL;

struct Node

{

    long long x;

    long long y;

    long long s;

}node[];

int cmp(const Node s1,const Node s2)

{

    if(s1.x==s2.x)

        return s1.y<s2.y;

    return s1.x<s2.x;

}

LL PowMod(LL a,LL b,LL MOD)

{

    LL ret=;

    while(b)

    {

        if(b&) ret=(ret*a)%MOD;

        a=(a*a)%MOD;

        b>>=;

    }

    return ret;

}

LL fac[];

LL Get_Fact(LL p)

{

    fac[]=;

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

        fac[i]=(fac[i-]*i)%p;

}

LL calc(LL n,LL m,LL p)

{

    LL ret=;

    while(n&&m)

    {

        LL a=n%p,b=m%p;

        if(a<b) return ;

        ret=(ret*fac[a]*PowMod(fac[b]*fac[a-b]%p,p-,p))%p;

        n/=p;

        m/=p;

    }

    return ret;

}

int main()

{

    long long n,m;

    int Case=,k,T;

    Get_Fact(mod);

    //cout<<calc(2,0,mod);

    cin>>T;

    while(T--)

    {

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

        int tot=;

        long long sum=;

        long long x,y;

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

        {

            scanf("%lld%lld",&x,&y);

            if(x->=&&y->=) { node[tot].x=x-; node[tot].y=y-; tot++; }

            if(x->=&&y>=) { node[tot].x=x-; node[tot].y=y; tot++; }

            if(x->=&&y+>=) { node[tot].x=x-; node[tot].y=y+; tot++; }

            if(x>=&&y->=) { node[tot].x=x; node[tot].y=y-; tot++; }

            if(x>=&&y+>=) { node[tot].x=x; node[tot].y=y+; tot++; }

            if(x+>=&&y->=) { node[tot].x=x+; node[tot].y=y-; tot++; }

            if(x+>=&&y>=) { node[tot].x=x+; node[tot].y=y; tot++; }

            if(x+>=&&y+>=) { node[tot].x=x+; node[tot].y=y+; tot++; }

            node[tot].x=x; node[tot].y=y; tot++;

        }

        if(tot>)

        sort(node,node+tot,cmp);

        //cout<<x<<y<<endl;

        //for(int i=0;i<tot;i++)

        //cout<<"tot: "<<node[i].x<<" "<<node[i].y<<endl;

        sum=calc(n+m-,n-,mod)%mod;

        // cout<<"n: "<<n<<" m: "<<m<<endl;

        //cout<<tot<<endl;

        //cout<<sum<<endl;

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

        {

            node[i].s=calc(node[i].x+node[i].y-,node[i].x-,mod)%mod;

        }

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

        {

            long long tt=calc(n-node[i].x+m-node[i].y,m-node[i].y,mod);

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

            {

                if(node[j].y>=node[i].y)

                {

                    long long d1=node[j].y-node[i].y;

                    long long d2=node[j].x-node[i].x;

                    node[j].s=(node[j].s-(node[i].s*calc(d1+d2,d1,mod))%mod)%mod;

                }

            }

            sum=(sum-(node[i].s*tt)%mod)%mod;

            sum = (sum%mod+mod)%mod;

        }

        printf("Case #%d: %lld\n",Case++,sum);

    }

}