这个题我整整对着题解看了一晚上才完全的想明白

因为这个题说（x2-x1）^2 +（y2-y1）^2 = 5，很容易想到1+4=5

也就是说，每走一步，距离起点的曼哈顿距离就增加3（一个方向走1步，另一个走2步）

画个图，发现是个斜着的杨辉三角

所以我们可以用组合数公式去算到这个点一共有多少种方案

因此我们可以一步步算出障碍物到起点的方案，然后减去前面障碍物到现在这个点的方案

因为数据范围较大，递推组合数不现实，我们需要用卢卡斯定理来快速算出组合数

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int mo=110119;typedef long long LL;LL h,w,n,cas=1,f[mo+10],all[mo+10];LL dp[2010];inline void init() { f[1]=f[0]=all[1]=1; for(int i=2;i<=mo;i++) f[i]=f[i-1]*i%mo,all[i]=all[mo%i]*(mo-mo/i)%mo;//f数组存的是阶乘%mo，all数组存的是阶乘逆元 }/*逆元证明过程（限p为素数） 设x=p%a,y=p/ax+y*a=p;(x+y*a)%p =0x%p+y*a%p=0x%p=(-y)*a%px%p*inv(a)=(-y)%pinv(a)=inv(x)*(p-y)%pinv(a)=inv(p%a)*(p-p/a)%p */ struct in{ LL x,y;}poi[2010];bool cmp(in a,in b){ return a.x
           
            n) return 0; if(m==n) return 1; if(m<0) return 0; return f[n]*all[f[m]]%mo*all[f[n-m]]%mo;}inline LL lucas(LL n,LL m){ if(m==0) return 1; return C(n%mo,m%mo)*lucas(n/mo,m/mo)%mo; /*else不知道为啥非递归错了qwq { LL re=1; while(n>0&&m>0) { re=((re%mo)*(C(n%mo,m%mo)%mo))%mo; n/=mo,m/=mo; } return re; }*/}int main(){ init();//预处理 while(~scanf("%lld%lld%lld",&h,&w,&n)) { bool flag=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%lld%lld",&poi[i].x,&poi[i].y); if(poi[i].x==h&&poi[i].y==w)//如果终点有障碍物就无法到达 flag=1; poi[i].x--,poi[i].y--; } sort(poi+1,poi+1+n,cmp); poi[++n]=(in){h-1,w-1}; if((poi[n].x+poi[n].y)%3!=0||flag)//如果终点不满足（x+y）%3==0的性质则到不了 { printf("Case #%lld: %d\n",cas++,0); continue; } for(int i=1;i<=n;i++) { if((poi[i].x+poi[i].y)%3==0)//如果该点有到达的可能性（并不是一定存在，如（6,0）） { LL low=(poi[i].x+poi[i].y)/3;//求走了多少次 LL high=min(poi[i].x,poi[i].y)-low;//求走的次数较少的方向走了几次 dp[i]=lucas(low,high)%mo;//求在走了low次，有high次走向走的次数较少的方向的时候的方案数 //可以想象成一个平行四边形，假设走一次的长度为一个单位，那么短边+长边=low,短边=high for(int j=1;j