hdu5794

从(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)转移即可

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 typedef long long ll;

 using namespace std;

 const int mo=;

 struct node{ll x,y;} a[];

 int f[],jc[mo+],ni[mo+];

 ll n,m;

 int t,tt;

 bool cmp(node a,node b)

 {

   if (a.x==b.x) return a.y<b.y;

   return a.x<b.x;

 }

 ll quick(ll x,int y)

 {

   ll s=;

   while (y)

   {

     if (y&) s=s*x%mo;

     x=x*x%mo; y>>=;

   }

   return s;

 }

 int c(int n,int m)

 {

   if (n<||m<||m>n) return ;

   else return 1ll*jc[n]*ni[m]%mo*ni[n-m]%mo;

 }

 int lucas(ll n,ll m)

 {

   if (n<||m<||m>n) return ;

   int ans=;

   while (n||m)

   {

     ans=1ll*ans*c(n%mo,m%mo)%mo;

     n/=mo; m/=mo;

   }

   return ans;

 }

 int main()

 {

   jc[]=; ni[]=;

   for (int i=; i<mo; i++)

   {

     jc[i]=1ll*jc[i-]*i%mo;

     ni[i]=quick(jc[i],mo-);

   }

   while (scanf("%lld%lld%d",&n,&m,&t)!=EOF)

   {

     for (int i=; i<=t; i++) scanf("%lld%lld",&a[i].x,&a[i].y);

     a[++t]=(node){n,m};

     sort(a+,a+t+,cmp);

     memset(f,,sizeof(f));

     for (int i=; i<=t; i++)

     {

       if ((a[i].x+a[i].y-)%) continue;

       else f[i]=lucas((a[i].x+a[i].y-)/,(2ll*a[i].x-a[i].y-)/);

       for (int j=; j<i; j++)

       {

         if (a[i].x<a[j].x||a[i].y<a[j].y||(a[i].x+a[i].y-a[j].x-a[j].y)%) continue;

         f[i]=(f[i]-1ll*f[j]*lucas((a[i].x+a[i].y-a[j].x-a[j].y)/,(2ll*(a[i].x-a[j].x)-(a[i].y-a[j].y))/)%mo+mo)%mo;

       }

     }

     printf("Case #%d: %d\n",++tt,f[t]);

   }

   return ;

 }