hdu5794 A Simple Chess 容斥+Lucas 从(1,1)开始出发，每一步从(x1,y1)到达(x2,y2)满足(x2−x1)^2+(y2−y1)^2=5, x2>x1,y2>y1; 其实就是走日字。而且是往(n,m)方向走的日字。还有r个障碍物，障碍物不可以到达。求(1,1)到(n,m)的路径条数。

A Simple Chess

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2597 Accepted Submission(s): 691

Problem Description

There is a

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

Sample Output

Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 1
Case #5: 5

Author

UESTC

Source

2016 Multi-University Training Contest 6

/**
题目：A Simple Chess
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5794
题意：从(1,1)开始出发，每一步从(x1,y1)到达(x2,y2)满足(x2−x1)^2+(y2−y1)^2=5, x2>x1,y2>y1;
其实就是走日字。而且是往(n,m)方向走的日字。还有r个障碍物，障碍物不可以到达。求(1,1)到(n,m)的路径条数。
思路：容斥+Lucas

如果没有障碍物：那么每一次可以选择从(x1,y1)到达(x1+2,y1+1)或者(x1+1,y1+2)；
那么设选择了x次(x1+2,y1+1),y次(x1+1,y1+2)
那么： x1+2*x+y = n;  => 2*x+y = n-x1;
       x+2*y+y1 = m;     2*y+x = m-y1;

x = (2*n-2*x1-m+y1)/3;
y = (2*m-2*y1-n+x1)/3;  说明如果2*n-2*x1-m+y1或者2*m-2*y1-n+x1不是3的倍数，（x,y都必须非负整数），那么无法到达。

否则路径条数为：C(x+y,x)；

存在障碍物：
假设只有一个障碍物，那么用总的路径条数sum-经过这一个障碍物的路径条数dp[1]。
假设存在两个障碍物，那么sum-经过的第一个障碍物为编号1的路径条数-经过的第一个障碍物为编号2的路径条数。（注意：第一个！！！）

经过的第一个障碍物为编号1的路径条数：从(1,1)到达(x1,y1)的路径条数乘以(x1,y1)到达(n,m)的路径条数。
经过的第一个障碍物为编号2的路径条数：（从(1,1)到达(x2,y2)的路径条数-从(1,1)到达(x1,y1)然后从(x1,y1)到达(x2,y2)的路径条数）
乘以 从(x2,y2)到达(n,m)的路径条数。

当多个障碍物时，方法同上处理。

处理c(x+y,x)%mod用Lucas定理。
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int maxn = 1e6+10;
const int mod = 110119;
LL f[mod+10];///阶乘。
LL inv[mod+10];///逆元
LL exgcd(LL a, LL b, LL &x, LL &y)///扩展欧几里得；
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL gcd = exgcd(b, a % b, x, y);
    LL t = x;
    x = y;
    y = t - (a / b) * x;
    return gcd;
}
LL inverse(LL num, LL mod)///求逆元；
{
    LL x, y;
    exgcd(num, mod, x, y);
    return (x % mod + mod) % mod;
}
void init()///如果mod小，那么可以线性筛逆元。
{
    inv[1] = 1;
    for(int i = 2; i < mod; i++){
        inv[i] = (mod-mod/i)*inv[mod%i]%mod;
    }
    f[0] = 1;
    for(int i = 1; i < mod; i++){///预处理阶乘。
        f[i] = f[i-1]*i%mod;
    }
}
LL mult(LL a,LL b,LL p)///解决 大数a*b%p溢出long long 的方法；
{
    LL ans=0;
    while(b)
    {
        if(b&1)
            ans=(ans+a)%p;
        b>>=1;
        a=(a+a)%p;
    }
    return ans;
}
LL C(LL a, LL b, LL mod)///实现C(n,m)%p
{

    if (b > a)
        return 0;
    return mult(mult(f[a],inv[f[b]],mod),inv[f[a-b]],mod);/// a!/(b!*(a-b)!);
}
LL lucas(LL n, LL m, LL p)///卢卡斯定理实现；c(n,m)%p；
{
    if (m == 0)
        return 1;
    return mult(C(n % p, m % p, p),lucas(n / p, m / p, p),p);
}
LL solve(LL x1,LL y1,LL n,LL m)
{
    if((2*n-2*x1-m+y1)%3!=0) return 0;
    if((2*m-2*y1-n+x1)%3!=0) return 0;
    LL x = (2*n-2*x1-m+y1)/3;
    LL y = (2*m-2*y1-n+x1)/3;
    if(x<0||y<0) return 0;
    return lucas(x+y,y,mod)%mod;
}
LL n, m, r;
struct node
{
    LL x, y;
    bool operator < (const node&k)const{
        if(x==k.x) return y<k.y;
        return x<k.x;
    }
}t[104];
LL ans[104];
int main()
{
    int cas = 1;
    init();///初始化逆元。
    while(scanf("%lld%lld%lld",&n,&m,&r)!=EOF)
    {
        for(int i = 0; i < r; i++){
            scanf("%lld%lld",&t[i].x,&t[i].y);
        }
        sort(t,t+r);

        LL sum = solve(1,1,n,m);
        for(int i = 0; i < r; i++){
            ans[i] = solve(1,1,t[i].x,t[i].y);
            for(int j = 0; j < i; j++){
                ans[i] = (ans[i]-ans[j]*solve(t[j].x,t[j].y,t[i].x,t[i].y)%mod+mod)%mod;
            }
        }
        //cout<<"sum = "<<sum<<endl;
        //cout<<"ans[0] = "<<ans[0]<<endl;
        for(int i = 0; i < r; i++){
            sum = (sum-ans[i]*solve(t[i].x,t[i].y,n,m)%mod+mod)%mod;
        }
        printf("Case #%d: %lld
",cas++,sum);
    }
    return 0;
}