首页 > > 程序设计 > C/C++ >

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

2018-06-17 23:39:44来源：未知阅读 ()

题目链接

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=997;
typedef long long LL;
struct Node
{
    long long x;
    long long y;
    long long s;
}node[105];

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=1;
    while(b)
    {
        if(b&1) ret=(ret*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return ret;
}
LL fac[1000005];
LL Get_Fact(LL p)
{
    fac[0]=1;
    for(int i=1; i<=p; i++)
        fac[i]=(fac[i-1]*i)%p;
}
LL calc(LL n,LL m,LL p)
{
    LL ret=1;
    while(n&&m)
    {
        LL a=n%p,b=m%p;
        if(a<b) return 0;
        ret=(ret*fac[a]*PowMod(fac[b]*fac[a-b]%p,p-2,p))%p;
        n/=p;
        m/=p;
    }
    return ret;
}

int main()
{
    long long n,m;
    int Case=1,k,T;
    Get_Fact(mod);
    //cout<<calc(2,0,mod);
    cin>>T;
    while(T--)
    {
        scanf("%lld%lld%d",&n,&m,&k);
        int tot=0;
        long long sum=0;
        long long x,y;
        for(int i=0;i<k;i++)
        {
            scanf("%lld%lld",&x,&y);
            if(x-1>=1&&y-1>=1) { node[tot].x=x-1; node[tot].y=y-1; tot++; }
            if(x-1>=1&&y>=1) { node[tot].x=x-1; node[tot].y=y; tot++; }
            if(x-1>=1&&y+1>=1) { node[tot].x=x-1; node[tot].y=y+1; tot++; }
            if(x>=1&&y-1>=1) { node[tot].x=x; node[tot].y=y-1; tot++; }
            if(x>=1&&y+1>=1) { node[tot].x=x; node[tot].y=y+1; tot++; }
            if(x+1>=1&&y-1>=1) { node[tot].x=x+1; node[tot].y=y-1; tot++; }
            if(x+1>=1&&y>=1) { node[tot].x=x+1; node[tot].y=y; tot++; }
            if(x+1>=1&&y+1>=1) { node[tot].x=x+1; node[tot].y=y+1; tot++; }
            node[tot].x=x; node[tot].y=y; tot++;
        }
        if(tot>0)
        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-2,n-1,mod)%mod;
        // cout<<"n: "<<n<<" m: "<<m<<endl;
        //cout<<tot<<endl;
        //cout<<sum<<endl;

        for(int i=0;i<tot;i++)
        {
            node[i].s=calc(node[i].x+node[i].y-2,node[i].x-1,mod)%mod;
        }
        for(int i=0;i<tot;i++)
        {
            long long tt=calc(n-node[i].x+m-node[i].y,m-node[i].y,mod);
            for(int j=i+1;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);
    }
}