JAG夏合宿2010 Day2 Problem F 10歳の動的計画法

問題

道が碁盤の目状の街において、
家(0,0)から学校(N,M)まで、←または↓への移動をちょうどK回だけして辿り着く方法は何通りあるか。

X座標またはY座標が負になるような点には入ることはできないが、
X座標がNを超える、またはY座標がMを超えるような点に入ることは出来る。

制約条件

N,M≦100000
K≦10000

方針

解説スライドの通りである。
左への移動をi回として、iを0からKまでそれぞれの場合について求め、足し合わせる。
更に、縦の移動と横の移動は独立して考え、それぞれを掛け合わせる。

左にi回移動して、（途中で座標が負にならず）座標Nまで辿り着く場合の数はどうやって求めるか。
これは次のように考える。
N+2i回の右移動とi回の左移動を、条件を満たすように並べ替える場合の数である。
すなわち、碁盤の目において、
(0,0)から(i,N+i)まで、y>xを満たしながら移動する場合の数である。
これはゴールをGとして、Gを直線y=x-1について折り返したような点をG'とすれば、
(Gへ行く場合の数)-(G'へ行く場合の数)で求められる。

それぞれはコンビネーションで計算でき、それは、階乗を事前に計算しておくことで、
O(log n)くらいで計算できる。

ソースコード

invModはspaghetti sourceのコードなので省略。

int fact[MAX];
int N,M,K;
int C(int n,int k){
  return fact[n]*invMod(fact[n-k],mod)%mod*invMod(fact[k],mod)%mod;
}
int calc(int n,int p){
  return C(n+2*p,p)*(n+1ll)%mod*invMod(n+p+1,mod)%mod;
}
int main(){
  cin>>N>>M>>K;
  
  fact[0]=1;
  for(int i=1;i<MAX;i++)fact[i]=(ll)fact[i-1]*i%mod;
  
  int ans=0;
  for(int i=0;i<=K;i++){
    (ans+=(ll)calc(N,i)*calc(M,K-i)%mod*C(N+M+2*K,N+2*i)%mod)%=mod;
  }
  cout<<ans<<endl;
  return 0;
}int fact[MAX];
int N,M,K;
int C(int n,int k){
  return fact[n]*invMod(fact[n-k],mod)%mod*invMod(fact[k],mod)%mod;
}
int calc(int n,int p){
  return C(n+2*p,p)*(n+1ll)%mod*invMod(n+p+1,mod)%mod;
}
int main(){
  cin>>N>>M>>K;
  
  fact[0]=1;
  for(int i=1;i<MAX;i++)fact[i]=(ll)fact[i-1]*i%mod;
  
  int ans=0;
  for(int i=0;i<=K;i++){
    (ans+=(ll)calc(N,i)*calc(M,K-i)%mod*C(N+M+2*K,N+2*i)%mod)%=mod;
  }
  cout<<ans<<endl;
  return 0;
}