处理阶乘有三种办法:
(1)传统意义上的直接递归,n的规模最多到20+,太小了,在本题不适用,而且非常慢
(2)稍快一点的算法,就是利用log()化乘为加,n的规模虽然扩展到1000+,但是由于要用三重循环,一旦n规模变得更大,耗时就会非常之严重,时间复杂度达到O(n*m*(n-m)),本题规定了n,m用unsigned
int32类型,就是说n,m的规模达到了21E以上,铁定TLE的。而且就算抛开时间不算,还存在一个致命的问题,就是精度损失随着n的增加会变得非常严重。
因为n有多大,就要进行n次对数运算,n规模一旦过大,就会丢失得非常严重了。所以这种方法是绝对不可取的,因为中途的精度丢失不是简单的四舍五入可以挽回的。
(3)拆分阶乘,逐项相除,再乘以前面所有项之积。这种方法用一个循环就OK了,时间复杂度只有O(n-m),非常可观。
---------------------以上转自小优的博客-----------------------------------------------------
我只知道第一种方法加c(m,n)=c(m-1,n)+c(m-1,n-1)这个。显然根本不知道还可以用第三种方法double这么做,我以为,,,我以为
还要注意看是数据是unsigned的类型
1 #include <stdio.h> 2 unsigned find(unsigned a,unsigned b){ 3 double res=1; 4 b=b<(a-b)?b:(a-b); 5 while(b){ 6 res*=(double)(a--)/(double)(b--); 7 } 8 res+=0.5; 9 return (unsigned)res; 10 } 11 int main(){ 12 unsigned m,n; 13 while(~scanf("%u%u",&m,&n)){ 14 if(m==0&&n==0) break; 15 printf("%u\n",find(m+n,m)); 16 } 17 return 0; 18 }