HDU 5794 A Simple Chess Lucas定理+dp

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

题意概述：
　　给出一个N*M的网格。网格上有一些点是障碍，不能经过。行走的方式是向右下角跳马步。求有多少种方案可以从(1,1)走到(N,M)。
　　多组数据，组数不超过25。N,M<=1e18。

分析：

　　还是水题。。。（我写这个的原因只是因为我第一次用lucas）分析一下可以发现横跳和纵跳各自的步数是确定的，所以变成了一个组合数问题。

　　当有障碍的时候按照第一次碰到的障碍分类，先把棋盘当成完全没有障碍，然后扣掉这些方案即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 #include<vector>

 #include<cctype>

 using namespace std;

 const int mo=;

 typedef long long LL;

 LL N,M,R;

 int inv[mo],J[mo],Ji[mo];

 struct XY{

     LL x,y;

     friend bool operator < (XY a,XY b){

         return a.x<b.x||a.x==b.x&&a.y<b.y;

     }

     friend bool operator == (XY a,XY b){

         return a.x==b.x&&a.y==b.y;

     }

 }p[];

 int f[];

 int Lucas(LL x,LL y)

 {

     if(x<y) return ;

     if(x<mo&&y<mo) return 1ll*J[x]*Ji[x-y]%mo*Ji[y]%mo;

     return 1ll*Lucas(x/mo,y/mo)*Lucas(x%mo,y%mo)%mo;

 }

 void ready()

 {

     inv[]=;

     for(int i=;i<mo;i++)

         inv[i]=1ll*inv[mo%i]*(mo-mo/i)%mo;

     J[]=,Ji[]=;

     for(int i=;i<mo;i++){

         J[i]=1ll*J[i-]*i%mo;

         Ji[i]=1ll*Ji[i-]*inv[i]%mo;

     }

 }

 int solve(LL n,LL m)

 {

     if((*n-m-)<||(*n-m-)%||(*m-n-)<||(*m-n-)%) return ;

     LL a=(*m-n-)/,b=(*n-m-)/;

     return Lucas(a+b,b);

 }

 int main()

 {

     ready();

     int T=;

     while(cin>>N>>M>>R){

         int ans=solve(N,M);

         if(R){

             for(int i=;i<=R;i++)

                 cin>>p[i].x>>p[i].y;

             sort(p+,p+R+);

             R=unique(p+,p+R+)-p-;

             memset(f,,sizeof(f));

             for(int i=;i<=R;i++){

                 f[i]=solve(p[i].x,p[i].y);

                 for(int j=;j<i;j++)if(p[j].x<p[i].x&&p[j].y<p[i].y)

                     f[i]=(f[i]-1ll*f[j]*solve(p[i].x-p[j].x+,p[i].y-p[j].y+)%mo+mo)%mo;

             }

             for(int i=;i<=R;i++)

                 ans=(ans-1ll*f[i]*solve(N-p[i].x+,M-p[i].y+)%mo+mo)%mo;

         }

         cout<<"Case #"<<++T<<": "<<ans<<'\n';

     }

     return ;

 }

巴特西

HDU 5794 A Simple Chess Lucas定理+dp

最新文章

热门文章