// 356K 16MS G++
// 356K 0MS G++ add m ==0 check
// 356K 16MS G++
// 356K 0MS G++ add m ==0 check
#include <stdio.h>
#include <string.h>
#include <math.h>
int m;
int n;
// void getNum(unsigned int n, unsigned int m) {
// // long long total = n;
// m = m < (n -m) ? m : (n -m);
// if (m == 0) {
// printf("1\n");
// return;
// }
// long long cnm = 1;
// for (long i = 1; i <=m ; i++) {
// cnm = cnm*(n-i+1)/i;
// }
// printf("%lld\n", cnm);
// }
void getNum(unsigned int n, unsigned int m) {
if (m == 0 || m == n) {
printf("1\n");
return;
}
m = m < (n -m) ? m : (n -m);
double cnm = 1.0;
while(m>0)
cnm *= (double)(n--)/(double)(m--);
cnm+=0.5;
printf("%lld\n", (long long)cnm);
}
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
if (!m && !n) {
return 0;
} else if (!n) {
printf("0\n");
} else if (!m) {
printf("1\n");
} else{
getNum(n, m);
}
}
}
要说算是道水题, 重点考察:
C(n,m) = C(n,m-1) * (n-m+1) / m.
C(n,m) = C(n,n-m).
尤其是第二个公式, 如果不做这个检测(取m 和 n-m中最小的 来求组合数),铁定TLE,题目的测试数据也应该都是这种类型的, n-m 或 m中会有一个很小的数,使得运算量不会很大(题目很贴心的说了结果
it will be less than 2
31) , 一开始还以为是道超级水题,直接把二维数组递推求组合搞上去,结果果真RE,然后使用之前用过的组合优化求法, 以及 上面的公式(分别对应code里两个getNum()), 都得到了0ms的结果