Train Problem II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1840    Accepted Submission(s): 1080

1
2
3
10

1
2
5
16796

Hint
The result will be very large, so you may not process it by 32-bit integers.
 

#include <stdio.h><br /> #include <string.h><br /> #define MAXLEN 101<br /> #define MAXCASE 101<br /> int catalan[MAXCASE][MAXLEN];<br /> int temp[MAXLEN];<br /> int main(void)<br /> {<br /> int i, j;<br /> int mode = 0, res = 0, n = 0;<br /> memset(catalan, 0, sizeof(catalan));<br /> catalan[1][0] = 1;<br /> for(i = 2; i < MAXCASE; i++)<br /> {<br /> mode = 4 * i - 2;<br /> for(j = 0; j < MAXLEN; j++)<br /> {<br /> catalan[i][j] = catalan[i-1][j] * mode;<br /> if(catalan[n][j] >= 10)<br /> {<br /> catalan[i][j+1] += catalan[i][j] / 10;<br /> catalan[i][j] %= 10;<br /> }<br /> }<br /> memset(temp, 0, sizeof(temp));<br /> mode = i + 1;<br /> res = 0;<br /> for(j = MAXLEN-1; j >= 0; j--)<br /> {<br /> temp[j] = (res * 10 + catalan[i][j]) / mode;<br /> res = (res * 10 + catalan[i][j]) % mode;<br /> }<br /> for(j = 0; j < MAXLEN; j++)<br /> {<br /> catalan[i][j] = temp[j];<br /> }<br /> }<br /> while(scanf("%d", &n) == 1)<br /> {<br /> j = MAXLEN - 1;<br /> while(catalan[n][j] == 0)<br /> {<br /> j--;<br /> }<br /> printf("%d", catalan[n][j]);<br /> while(j--)<br /> {<br /> printf("%d", catalan[n][j]);<br /> }<br /> printf("/n");<br /> }<br /> return 0;<br /> } 

方法：卡特兰公式 

技巧：大数的乘法和除法，用数组表示大数的每一位，且大数的每一位从地位到高位放对应数组的0－MAXLEN－1，这样，作乘法是直接从0             开始循环数组，作除法是需要从MAXLEN－1开始向0下标循环数组

感谢http://www.wutianqi.com/?p=1281的作者的提示