HDU 5794 A Simple Chess (容斥+lucas定理)

57 阅读 0 评论 38 点赞

我是靠谱客的博主悲凉发带，最近开发中收集的这篇文章主要介绍HDU 5794 A Simple Chess (容斥+lucas定理)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给你一个很大的棋盘，然后让你走日字，从（1，1）走到（n，m），有多少种方法，但是里面有一些障碍，不能走到障碍处

走的方法，那肯定是lucas定理求组合数就行了，但是不走到障碍，就这就需要容斥了，但是有100个障碍，肯定不是那种二进制枚举的容斥，应该是先把所有的障碍排序，然后dp[i]表示走到这个障碍物处，不经过前面所有的障碍物的位置。
所以这题就是100*100的枚举dp容斥，先算出来从（1，1）到这里有多少种方法，再减去在他前面的所有障碍到他的方法，因为前面所有障碍的答案都是不相交的，所以算出来也是不经过前面所有障碍的方法.
注意可能终点处有障碍就行了。

代码：

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;
#define   MAX           400005
#define   MAXN          1000005
#define   maxnode       205
#define   sigma_size    26
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   lrt           rt<<1
#define   rrt           rt<<1|1
#define   middle        int m=(r+l)>>1
#define   LL            long long
#define   ull           unsigned long long
#define   mem(x,v)      memset(x,v,sizeof(x))
#define   lowbit(x)     (x&-x)
#define   pii           pair<int,int>
#define   bits(a)       __builtin_popcount(a)
#define   mk            make_pair
#define   limit         10000

//const int    prime = 999983;
const int    INF   = 0x3f3f3f3f;
const LL     INFF  = 0x3f3f;
const double pi    = acos(-1.0);
const double inf   = 1e18;
const double eps   = 1e-4;
const LL    mod    = 1e9+7;
const ull    mx    = 133333331;

/*****************************************************/
inline void RI(int &x) {
      char c;
      while((c=getchar())<'0' || c>'9');
      x=c-'0';
      while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
 }
/*****************************************************/

pair<LL,LL> p[105];
LL dp[105];
LL fact[110119+5];
LL mo=110119;
void Getfact(LL p){
    fact[0]=1;
    for(int i=1;i<p;i++){
        fact[i]=(fact[i-1]*i)%p;
    }
}

LL qpow(LL a,LL n,LL p){
    LL ans=1;
    while(n){
        if(n&1) ans=ans*a%p;
        a=a*a%p;
        n>>=1;
    }
    return ans;
}

LL Lucas(LL n,LL m,LL p){
    LL ans=1;
    while(n&&m){
        LL a=n%p,b=m%p;
        if(a<b) return 0;
        ans=(ans*fact[a]*qpow(fact[b]*fact[(a-b)]%p,p-2,p))%p;
        n/=p;
        m/=p;
    }
    return ans;
}

LL cal(LL a,LL b){
    if((2*b-a)%3!=0||2*b<a) return 0;
    LL x2=(2*b-a)/3;
    LL x1=b-2*x2;
    if(x1<0) return 0;
    return Lucas(x1+x2,x1,mo);
}

int main(){
    //freopen("in.txt","r",stdin);
    LL n,m;
    int r;
    int kase=0;
    while(cin>>n>>m>>r){
        kase++;
        Getfact(110119);
        int flag=0;
        for(int i=0;i<r;i++){
            LL a,b;
            scanf("%I64d%I64d",&a,&b);
            p[i]=mk(a,b);
            if(a==n&&b==m) flag=1;
        }
        if(flag){
            printf("Case #%d: ",kase);
            cout<<0<<endl;
            continue;
        }
        sort(p,p+r);
        for(int i=0;i<r;i++){
            dp[i]=cal(p[i].first-1,p[i].second-1);
            for(int j=0;j<i;j++){
                if(p[i].first>p[j].first&&p[i].second>p[j].second){
                    dp[i]=((dp[i]-cal(p[i].first-p[j].first,p[i].second-p[j].second)*dp[j])%mo+mo)%mo;
                }
            }
        }
        LL ans=cal(n-1,m-1);
        for(int i=0;i<r;i++){
            if(n>p[i].first&&m>p[i].second){
                ans=((ans-cal(n-p[i].first,m-p[i].second)*dp[i])%mo+mo)%mo;
            }
        }
        printf("Case #%d: ",kase);
        cout<<ans<<endl;
    }
    return 0;
}