10-Year-Old Dynamic Programming

10-Year-Old Dynamic Programming | Aizu Online Judge

ICPC　600点問題

問題概要
・からへの移動方法の数を求める
・但し最短ではなく、K回左か下に移動する
・第一象限しか移動できない

制約

解法
とりあえず上下や左右はさておいてx,y軸の移動に分ける
K回の寄り道を縦と横に分配する
x軸方向にi回寄り道するとx軸方向にはN+i回移動しないといけないので合計でN+2i回移動することになる
y軸方向はK-i回寄り道となるのでM+K-i回y軸方向に移動する　よって合計でM+2(k-i)回の移動になる
この移動方法の場合の数はK=0の要領で求められて
後は各軸方向の移動の順番を定める
この時負座標を各軸方向で取れないことに注意すると
x軸方向はとなる
（正直ここがあんまり良くわかってないが小ケースで手計算から推測した）
y軸方向も同様に求めて各iについての和をとれば解が求まる

…が実際は1000000007のmodを取る際にnCrをn/1 * (n-1)/2 *... の方法で求めると割り算の回数が増える関係で非常に効率が悪いという問題があり数回TLE
N+M+2K = 220000（実装は499999まで計算してある）までのfactorialのmod計算して割り算を1回にした方が速かった

#include <bits/stdc++.h>
 
using i64 = int64_t;
using namespace std;
const i64 MOD = 1000000007LL;
vector<i64> fact(500000);
 
inline i64 powermod(i64 a,i64 b){
  i64 r = 1LL;
  for(int i = 32 - __builtin_clz(b) - 1; i >= 0; i-- ){
    if((1 << i) & b) r = r * r % MOD * a % MOD;
    else r = r * r % MOD;
  }
  return r;
}
 
inline i64 divmod(i64 a,i64 b){
  return a * powermod(b,MOD-2) % MOD;
}
 
i64 nCr(i64 n,i64 r){
  if(r<0)return 0;
  i64 ne = fact[n];
  i64 di = fact[n-r] * fact[r] % MOD;
  return divmod(ne,di);
}
 
inline i64 A(i64 a,i64 b){
  return (nCr(a,b) + MOD - nCr(a,b-1)  ) % MOD;
}
 
int main() {
  i64 N,M,K;
  cin >> N >> M >> K;
   
  fact[0] = fact[1] = 1LL;
  for(int i = 2;i < 500000;i++){
    fact[i] = fact[i-1] * (i64)i % MOD;
  }
   
  i64 res = 0LL;
  for(i64 i = 0LL; i <= K; i++ ){
    res += nCr(N+M+K+K,N+i*2) * A(N+i*2,i) % MOD * A(M+(K-i)*2,K-i) % MOD;
    res %= MOD;
  }
   
  cout << res << endl;
}