2016暑假多校联合---A Simple Chess

Problem Description

There is a

.
Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.
I want you to tell me, There are how may ways the chess can achieve its goal.

Input

The input consists of multiple test cases.
For each test case:
The first line is three integers,

Output

For each test case,output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module

Sample Input

1 1 0

3 3 0

4 4 1

2 1

4 4 1

3 2

7 10 2

1 2

7 1

Sample Output

Case #1: 1

Case #2: 0

Case #3: 2

Case #4: 1

Case #5: 5

思路：先找马可以走到的点，可以发现点均分布在斜率为-1的直线上，个数为1、2、3、4…… 所以可以把这些点对应到第一象限，这些点分别为（1,1）（1,2）、（2,1）

（1,3）、（2,2）、（3,1）（1,4）（2,3）、（3,2）、（4,1）刚好充满第一象限，这时可以用组合数方便算出从某点到另一点的路径数，由于坐标很大，所以必须使用卢卡斯定理求组合数，注意去重，因为有障碍点。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <cmath>
using namespace std;
const long long mod=110119;
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 r;
    int Case=1;
    Get_Fact(mod);
    while(scanf("%lld%lld%d",&n,&m,&r)!=EOF)
    {
        int tot=0;
        long long sum=0;
        int flag=0;
        if((n+m+1)%3==0)
        {
            long long s=(n+m+1)/3;
            if(n>=s&&m>=s)
            {
                long long t=n;
                n=2*s-m;
                m=2*s-t;
            }
            else
            {
                flag=1;
            }
        }
        else
        {
            flag=1;
        }
        for(int i=0;i<r;i++)
        {
            long long x,y;
            scanf("%lld%lld",&x,&y);
            if((x+y+1)%3==0)
            {
                long long s=(x+y+1)/3;
                if(x>=s&&y>=s)
                {
                    node[tot].x=2*s-y;
                    node[tot].y=2*s-x;
                    if(node[tot].x<=n&&node[tot].y<=m)
                    tot++;
                }
            }
        }
        if(flag==1)
        {
            printf("Case #%d: %lld
",Case++,sum);
            continue;
        }
        if(tot>0)
        sort(node,node+tot,cmp);
        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++)
        //cout<<"tot: "<<node[i].x<<" "<<node[i].y<<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
",Case++,sum);
    }
}

2016暑假多校联合---A Simple Chess

相关推荐