PKU 1942-Paths on a Grid

問題概要

組合せを求めろ．ただし入出力が32Bit非負整数に収まることは保証される．

解法

k=0の場合とk=1の場合のみ答えをそく返すようにしてTLEを防ぐ

実装(C++)

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned int uint;
typedef long long lli;
lli comb(uint n,uint k){
	if(k==1)return n;
	if(k==0)return 1;
	if(k>n-k)return comb(n,n-k);
	lli res=1;
	bool ac[k];
	memset(ac,0,k);
	for(lli i=n;i>=n-k+1;i--){
		res*=i;
		for(lli i=1;i<=(int)k;i++){
			if(res%i==0&&ac[i-1]==false){
				res/=i;
				ac[i-1]=true;
			}
		}
	}

	return res;
}
int main() {
	uint x,y;
	while(cin>>x>>y){
		if(x==0&&y==0)break;
		cout<<comb(x+y,y)<<endl;
	}

	return 0;
}