pku1942-Paths on a Grid

本質上是組合數公式 一開始是用搜索模擬 太慢了

pku1942

Runtime Error
[cpp] 
#include<iostream> 
#include<stdio.h> 
using namespace std; 
 
__int64 dfs(__int64 x,__int64 y) 
{ 
    if(x==1||y==1) return 1; 
    return dfs(x-1,y)+dfs(x,y-1); 
} 
 
int main() 
{ 
    __int64 m,n; 
    while(scanf("%I64d%I64d",&m,&n),m+n) 
    { 
        printf("%I64d\n",dfs(m+1,n+1)); 
    } 
    return 0; 
} 

Accepted
[cpp] 
#include<iostream> 
using namespace std; 
 
__int64 C(__int64 n,__int64 m) 
{ 
    __int64 d,i; www.2cto.com
    if(m>n/2) m=n-m; 
    for(d=i=1;i<=m;i++)  d=d*(n-i+1)/i; 
    return d; 
} 
 
int main() 
{ 
    __int64 m,n; 
    while(scanf("%I64d%I64d",&m,&n),m+n) 
        printf("%I64d\n",C(m+n,m<n?m:n)); 
    return 0; 
}