PKU : 1942 - Paths on a Grid

数論

問題概要

http://poj.org/problem?id=1942

格子点のマップにおいて, 左下から右上までのパスの数を出力せよ.
出力値は, 2^32にはおさまる.

アルゴリズム

(w+h) Choose (h) を計算すればいいだけです.

プログラム

#include <iostream>
#include <map>
#include <cstring>
using namespace std;

typedef long long ll;

ll cmb(ll n, ll r){
  ll res = 1;
  if(n < 2 * r) r = n - r;
  for(ll i = 0; i < r; i++) res = (res * (n-i)) / (i+1);
  return res;
}

int main(){
  ll w,h;

  while(cin>>w>>h,w||h){
    cout<<cmb(w+h,h)<<endl;
  }
}