组合数（2019牛客国庆集训派对day1-B）
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K Special Judge, 64bit IO Format: %lld
judge：组合数
题目描述
给出
n
n
n 和
k
k
k，求
min
{
n
!
k
!
(
n
−
k
)
!
,
1
0
18
}
\min\{\frac{n!}{k! (n - k)!}, 10^{18}\}
min{k!(n−k)!n!,1018} 的值。 其中
n
!
=
1
×
2
×
⋯
×
n
n! = 1 \times 2 \times \cdots \times n
n!=1×2×⋯×n 表示
n
n
n 的阶乘。
输入描述:
输入文件包含多组数据，请处理到文件结束。 每组数据包含两个整数 n 和 k.
0
≤
k
≤
n
≤
1
0
9
0 \leq k \leq n \leq 10^9
0≤k≤n≤109
至多
1
0
5
10^5
105 组数据。
输出描述:
对于每组数据，输出一个整数，表示所求的值。
示例1
输入
1000000000 0
1000000000 2
1000000000 500000000
输出
1
499999999500000000
1000000000000000000
题解
暴力，但是需要注意数据溢出
代码（long double版）
#include<bits/stdc++.h>
using namespace std
;
long long INF
= 1e18;
int n
, m
;
long double c
;
int main() {
while (cin
>> n
>> m
) {
m
= min(n
- m
, m
);
c
= 1;
for (int i
= 1; i
<= m
; i
++) {
c
= c
* (n
- i
+ 1) / i
;
if (c
> INF
) break;
}
if (c
> INF
) cout
<< INF
<< endl
;
else cout
<< (long long)c
<< endl
;
}
}
代码（__int128版）
#include<bits/stdc++.h>
using namespace std
;
typedef __int128 ll
;
const ll INF
= 1e18;
const int N
= 2e3 + 10;
int n
, k
;
ll ans
;
int main() {
while (~scanf("%d%d", &n
, &k
)) {
if (k
> n
/ 2)k
= n
- k
;
ans
= 1;
for (int i
= 1; i
<= k
; ++i
) {
if (ans
*(n
- i
+ 1) / i
<= INF
)ans
= ans
* (n
- i
+ 1) / i
;
else {
ans
= INF
;
break;
}
}
printf("%lld\n", (ll
)ans
);
}
return 0;
}
