题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5794
A Simple Chess
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
#### 问题描述
> 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.
> Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.
> I want you to tell me, There are how may ways the chess can achieve its goal.
#### 输入
> The input consists of multiple test cases.
> For each test case:
> The first line is three integers, n,m,r,(1≤n,m≤1018,0≤r≤100), denoting the height of the board, the weight of the board, and the number of the obstacles on the board.
> Then follow r lines, each lines have two integers, x,y(1≤x≤n,1≤y≤m), denoting the position of the obstacles. please note there aren't never a obstacles at position (1,1).
#### 输出
> 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 110119.
#### 样例
> **sample input**
> 1 1 0
> 3 3 0
> 4 4 1
> 2 1
> 4 4 1
> 3 2
> 7 10 2
> 1 2
> 7 1
>
> **sample output**
> Case #1: 1
> Case #2: 0
> Case #3: 2
> Case #4: 1
> Case #5: 5
题意
n*m的大棋盘，有r个障碍物，你在1,1,并且每次只能往左下走日子步，问到达(n,m)的方案数
题解
Lucas+dp.
预备：设从i点到j点过程中走横日走了x步，走竖日走了y步，则有方程2x+y==n&&x+2y==m --x=(2n-m)/3,y=(2m-n)/3。
所以方案数为C[x+y][x]。这个需要用卢卡斯处理出来。先把所有障碍点从左上到右下排序。
dp[i]表示从1,1到(pt[i].x,pt[i].y)障碍的不经过任意其他位于它左上的障碍的情况数，则dp[i]=dp[i]-sigma(dp[j]*j到i点的所有方案数）。
代码
#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define pb(v) push_back(v)
#define sz() size()
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI=acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=111;
const int mod=110119;
const int maxm=mod+10;
LL n,m; int r;
pair<LL,LL> pt[maxn];
LL facinv[maxm],inv[maxm],fac[maxm];
LL dp[maxn];
LL get_C(LL n,LL m){
if(n<0||m<0||n<m) return 0;
return fac[n]*facinv[m]%mod*facinv[n-m]%mod;
}
LL Lucas(LL n,LL m,int mod){
if(m==0) return 1LL;
return get_C(n%mod,m%mod)*Lucas(n/mod,m/mod,mod)%mod;
}
LL calc(int i,int j){
LL n=pt[j].X-pt[i].X;
LL m=pt[j].Y-pt[i].Y;
if((n+m)%3) return 0;
LL sum=(n+m)/3;
if(n<0||m<0) return 0;
return Lucas(sum,n-sum,mod);
}
void pre(){
fac[0]=fac[1]=1;
facinv[0]=facinv[1]=1;//facinv[0]=1!!!!
inv[1]=1;
rep(i,2,maxm){
fac[i]=fac[i-1]*i%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
facinv[i]=facinv[i-1]*inv[i]%mod;
}
}
int main(){
pre();
int kase=0;
while(scanf("%lld%lld%d",&n,&m,&r)==3){
clr(dp,0);
int flag=0;
rep(i,1,r+1){
scanf("%lld%lld",&pt[i].X,&pt[i].Y);
if(pt[i].X==n&&pt[i].Y==m){
flag=1;
}
}
if(flag){
printf("Case #%d: 0\n",++kase);
continue;
}
pt[0].X=1,pt[0].Y=1;
pt[r+1].X=n,pt[r+1].Y=m;
sort(pt+1,pt+r+1);
dp[0]=1;
rep(i,1,r+2){
dp[i]=calc(0,i);
rep(j,1,i){
dp[i]-=dp[j]*calc(j,i)%mod;
dp[i]=(dp[i]%mod+mod)%mod;
}
}
printf("Case #%d: %lld\n",++kase,dp[r+1]);
}
return 0;
}
//end-----------------------------------------------------------------------