题目链接：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 ;
}