HDU 5794 A Simple Chess（数论）

Love The Way You Lie 2022-09-25 02:30 132阅读 0赞

There is a n×m board, a chess want to go to the position  
(n,m) from the position (1,1).The chess is able to go to position (x2,y2) from the position (x1,y1), only and if only x1,y1,x2,y2 is satisfied that (x2−x1)2+(y2−y1)2=5, x2>x1, y2>y1.

以上是部分题目无用

--------------------

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5794

题目大意：给你一个起点(1,1)，每次只能马字形行走，问到达最终的终点有多少种走法，中途会有一些障碍不能行走。

解题思路：  
很容易得出的结论：最终的答案就是不经过障碍能达到终点的所有方法，可以用起点到终点的总路径数减去会经过障碍的路径数。

那么如何求出起点到终点会经过障碍的方法数，考虑将给的障碍物按x从小到大排序。

我们记起点到点i不经过障碍物的路径数为num\[i\]  
记点i到点j的总路径数（可以经过障碍物）为cal(i,j)  
记起点为begin,终点为end。

对于第一个障碍物i，起点到i不会经过其它障碍物，所以i阻挡的路径就是起点到i的路径数乘以i到终点的路径数(即num\[i\]\*cal(begin,i)）。

对于第二个障碍物i+1，它挡住的路径会受第一个的影响，新挡住的路径就是num\[i+1\]\*cal(i+1,end)  
num\[i+1\]=cal(begin,i)-num\[i\]\*cal(i,i+1)。

对于第三个障碍物i+2，它新挡住的路径就是num\[i+2\]\*cal(i+2,end)，而num\[i+2\]=cal(begin,i+2)-num\[i\]\*cal(i,i+2)-num\[i+1\]\*cal(i+1,i+2)。

对于第n个障碍物,它新挡住路径是num\[n\]\*cal(n,end)，而num\[n\]=cal(begin,n)-num\[i\]\*cal(i,n)-num\[i+1\]\*cal(i+1,n)-num\[i+2\]\*cal(i+2,n)- - ->num\[n-1\]\*cal(n-1,n)。

把每个点新挡住的路径加起来就可以得到所有的被挡住的路径数，用cal(begin,end)减去其即可。

AC代码：

#include <iostream>
    #include <cstdlib>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <cstring>
    #include <map>
    #include <vector>
    #include <cmath>
    #include <stack>
    #include <queue>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    
    const ll mod=110119;
    const ll maxn=120000;
    
    ll fact[maxn];
    
    long long n,m,r;
    
    ll mod_comb(ll n,ll k, ll p);
    ll mod_fact(ll n,ll p, ll &e);
    ll mod_inverse(ll a,ll m);
    void init();//求组合数的四个函数,没用卢卡斯
    
    struct P
    {
        ll x;
        ll y;
    
    };
    vector<P> vec;
    
    bool judge(P p1,P p2)//判断两点是否能到达
    {
        ll x=p2.x-p1.x;
        ll y=p2.y-p1.y;
        if(2*x-y<0||2*y-x<0)  return false;
        ll x1=(2*x-y)/3;
        ll y1=(2*y-x)/3;
        if((x1*3)==(2*x-y)&&(y1*3)==(2*y-x)) return true;
        return false;
    }
    
    ll cal(P p1 ,P p2)//计算两点间的所有方法数
    {
        if(!judge(p1,p2)) return 0;
        ll x=p2.x-p1.x;
        ll y=p2.y-p1.y;
        ll x1=(2*x-y)/3;
        ll y1=(2*y-x)/3;
        if(x1<y1) swap(x1,y1);
        y1++;
        //向下走x1步和向右走y1步即可排列组合可计算不同走法
        return mod_comb(x1+y1-1,y1-1,mod)%mod;
    }
    
    ll abss(ll x)
    {
        if(x<0) return -x;
        return x;
    }
    
    bool cmp(P &p1,P &p2)//给点按x排序
    {
        if(p1.x==p2.x) return p1.y<p2.y;
        return p1.x<p2.x;
    }
    
    
    int main()
    {
        int cas=1;
        init();
        while(scanf("%I64d%I64d%I64d",&n,&m,&r)!=EOF)
        {
            vec.clear();
            P p2,p1;
            p2.x=n;
            p2.y=m;
            p1.x=1;
            p1.y=1;
            for(ll i=0; i<r; i++)
            {
                P p3;
                scanf("%I64d%I64d",&p3.x,&p3.y);
                if(judge(p1,p3)&&judge(p3,p2)) vec.push_back(p3);
            }
            printf("Case #%d: ",cas++);
            if(!judge(p1,p2))
            {
                printf("0\n");
                continue;
            }
            sort(vec.begin(),vec.end(),cmp);
            ll ans=cal(p1,p2);
            ll num[150];//存储起点到点i不经过障碍的路径数
    
            for(int i=0; i<vec.size(); i++)
            {
                ll ans1=0;
                for(int j=0;j<i;j++)
                {
                    ans1=(ans1+cal(vec[j],vec[i])*num[j])%mod;
                }
                num[i]=(cal(p1,vec[i])-ans1+mod)%mod;
                ans=((ans-num[i]*cal(vec[i],p2)%mod)+mod)%mod;
            }
            printf("%I64d\n",ans);
    
        }
    
        return 0;
    }
    
    
    
    void init()
    {
        fact[0]=1;
        ll res=1;
        for(ll i=1; i<maxn; i++)
        {
            res=(res*i)%mod;
            fact[i]=res%mod;
        }
    }
    ll extgcd(ll a,ll b, ll &x,ll& y)
    {
        ll d=a;
        if(b!=0)
        {
            d=extgcd(b,a%b,y,x);
            y-=(a/b)*x;
        }
        else
        {
            x=1;
            y=0;
        }
        return d;
    }
    
    
    ll mod_inverse(ll a,ll m)
    {
        ll x,y;
        extgcd(a,m,x,y);
        return (m+x%m)%m;
    }
    ll mod_fact(ll n,ll p, ll &e)
    {
        e=0;
        if(n==0) return 1;
        ll res=mod_fact(n/p,p,e);
        e+=n/p;
        if(n/p%2!=0) return res*(p-fact[n%p])%p;
        return res*fact[n%p]%p;
    }
    ll mod_comb(ll n,ll k, ll p)
    {
        if(n<0||k<0||n<k)return 0;
        ll e1,e2,e3;
        ll a1=mod_fact(n,p,e1);
        ll a2=mod_fact(k,p,e2);
        ll a3=mod_fact(n-k,p,e3);
        if(e1>e2+e3)return 0;
        return a1*mod_inverse(a2*a3%p,p)%p;
    
    }