题意：
给你n,m，从(1,1)到(n,m)，每次只能从左上到右下走日字路线，有k(<=100)的不能走的位置，问你有多少方案
题解：
画图可看到路线是一个杨辉三角的图，然后我们可以将对应的x,y转换到对应的点上，也可以吧杨辉三角看成一个平行四边形，
我这里看成的平行四边形，设dp[i]为从起点到第i个障碍物的的方案数，那么dp[i]=dp[i]-sum(dp[j]（第j个点能走到i这个点）*(j到i的方案数))。
然后我们把终点放到最后，最后求出的dp[end]就是答案
1 #include<cstdio> 2 #include<algorithm> 3 #define F(i,a,b) for(int i=a;i<=b;i++) 4 using namespace std; 5 typedef long long ll; 6 const ll P=110119; 7 ll f[P+5],r[P+5]; 8 ll C(ll n,ll m){return n<m?0:f[n]*r[n-m]%P*r[m]%P;} 9 ll lucas(ll n,ll m){ 10 if(n<m||m<0)return 0; 11 if(!m||n==m)return 1; 12 return C(n%P,m%P)*lucas(n/P,m/P)%P; 13 } 14 void init(){ 15 int i; 16 for(r[0]=r[1]=f[0]=f[1]=1,i=2;i<P;i++){ 17 f[i]=f[i-1]*i%P,r[i]=-r[P%i]*(P/i)%P; 18 while(r[i]<0)r[i]+=P; 19 } 20 for(i=2;i<P;i++)r[i]=r[i]*r[i-1]%P; 21 } 22 23 ll n,m,k,ic=1,dp[110]; 24 25 struct point{ 26 ll x,y; 27 bool operator<(const point &b)const{return x<b.x;} 28 }p[110]; 29 30 int main(){ 31 init(); 32 while(~scanf("%lld%lld%lld",&n,&m,&k)) 33 { 34 n--,m--; 35 int fg=0; 36 F(i,1,k) 37 { 38 scanf("%lld%lld",&p[i].x,&p[i].y),p[i].x--,p[i].y--; 39 if(p[i].x==n&&p[i].y==m)fg=1; 40 } 41 printf("Case #%lld: ",ic++); 42 if(n==0&&m==0)puts("1"); 43 else if((n+m)%3!=0||fg)puts("0"); 44 else 45 { 46 ll x,y,tx,ty; 47 sort(p+1,p+1+k); 48 p[++k].x=n,p[k].y=m; 49 F(i,1,k) 50 { 51 if((p[i].x+p[i].y)%3==0) 52 { 53 x=(p[i].x+p[i].y)/3,y=min(p[i].x,p[i].y)-x; 54 dp[i]=lucas(x,y); 55 F(j,1,i-1) 56 { 57 if(p[j].y<p[i].y&&p[j].x<p[i].x) 58 { 59 ll xx=p[i].x-p[j].x,yy=p[i].y-p[j].y; 60 if((xx+yy)%3==0) 61 { 62 ll tx=(xx+yy)/3,ty=min(xx,yy)-tx; 63 dp[i]-=(lucas(tx,ty)*dp[j])%P; 64 dp[i]=(dp[i]+P)%P; 65 } 66 } 67 } 68 } 69 } 70 printf("%lld ",dp[k]); 71 } 72 } 73 return 0; 74 }