HDU5794 A Simple Chess 容斥+lucas

分析：转自http://blog.csdn.net/mengzhengnan/article/details/47031777

一点感想：其实这个题应该是可以想到的，但是赛场上并不会

             dp[i]的定义很巧妙，容斥的思路也非常清晰

             然后就是讨论lucas的用法，首先成立的条件是mod是素数

             但是如果这个题mod很大，组合数取模感觉就不太可做了

             我认为当mod很大时，n应该很小可以预处理，但是n很大时mod应该比较小，这样也可以预处理

             如果n和mod都很大我就不会了。。。。

             这个题在预处理的时候，同样需要预处理逆元，如果用费马小定理的话，比较慢是O(nlogmod)的

             其实有更好的O(N)筛1到mod-1的算法

             详情请参考：http://blog.miskcoo.com/2014/09/linear-find-all-invert

             总的来说，赛场上没做出来还是太年轻

#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e2+5;
const LL mod = 110119;
struct Node{
  LL x,y;
  bool operator<(const Node &rhs)const{
    return x<rhs.x;
  }
}p[N];
int r,kase;
LL n,m,dp[N],f[mod+5],inv[mod+5];
LL C(LL n, LL m){
    if(m > n) return 0;
    return f[n]*inv[f[m]]%mod*inv[f[n-m]]%mod;
}
LL lucas(LL n, LL m){
    if(m == 0) return 1;
    return C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
}
int main(){
  f[1]=f[0]=inv[1]=1;
  for(int i=2;i<mod;++i){
    f[i]=f[i-1]*i%mod;
    inv[i]=inv[mod%i]*(mod-mod/i)%mod;
  }
  while(~scanf("%I64d%I64d%d",&n,&m,&r)){
    bool flag=false;
    for(int i=1;i<=r;++i){
      scanf("%I64d%I64d",&p[i].x,&p[i].y);
      if(p[i].x==n&&p[i].y==m)flag=true;
    }
    if(flag){
      printf("Case #%d: 0
",++kase);
      continue;
    }
    sort(p+1,p+1+r);
    memset(dp,0,sizeof(dp));
    ++r;p[r].x=n,p[r].y=m;
    for(int i=1;i<=r;++i){
      LL tx=p[i].x-1,ty=p[i].y-1,a=-1,b=-1;
      if((tx+ty)%3||(2*tx-ty)%3)continue;
      a=(2*tx-ty)/3;if(a<0)continue;
      b=(tx+ty)/3-a;if(b<0)continue;
      dp[i]=lucas(a+b,a);
      for(int j=1;j<i;++j){
        if(!dp[j])continue;
        if(p[i].x==p[j].x||p[i].y<=p[j].y)continue;
        tx=p[i].x-p[j].x,ty=p[i].y-p[j].y,a=-1,b=-1;
        if((tx+ty)%3||(2*tx-ty)%3)continue;
        a=(2*tx-ty)/3;if(a<0)continue;
        b=(tx+ty)/3-a;if(b<0)continue;
        if(a==0&&b==0)continue;
        dp[i]=(dp[i]-dp[j]*lucas(a+b,a)%mod+mod)%mod;
      }
    }
    printf("Case #%d: %I64d
",++kase,dp[r]);
  } 
  return 0;
}