从(u,v)到(n,m)相当于走x步1*2和y步2*1满足 x+2y=n-u,2x+y=m-v

解方程然后组合计数即可。

以前没写过lucas定理，写一下……

其实就是C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

顺便这题的容斥有特殊性，只要把点排序，然后用f[i]表示到第i个障碍且路上没有经过其他障碍的方案即可，O(c^2)转移即可

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 typedef long long ll; 7 using namespace std; 8 const int mo=110119; 9 struct node{ll x,y;} a[110];10 int f[110],jc[mo+1],ni[mo+1];11 ll n,m;12 int t,tt;13 bool cmp(node a,node b)14 {15   if (a.x==b.x) return a.y
           
            >=1;26 }27 return s;28 }29 30 int c(int n,int m)31 {32 if (n<0||m<0||m>n) return 0;33 else return 1ll*jc[n]*ni[m]%mo*ni[n-m]%mo;34 }35 36 int lucas(ll n,ll m)37 {38 if (n<0||m<0||m>n) return 0;39 int ans=1;40 while (n||m)41 {42 ans=1ll*ans*c(n%mo,m%mo)%mo;43 n/=mo; m/=mo;44 }45 return ans;46 }47 48 int main()49 {50 jc[0]=1; ni[0]=1;51 for (int i=1; i