组合

原题链接：https://ac.nowcoder.com/acm/contest/1099/B

这道题的关键要点有三个：

1.把公式化简

2.把k变大

即：  

ll f(ll n,ll k) { //k+1 k+2....n //1 2 3 ...n-k //if(k<n/2)k=n-k; __int128 ans=1; for(ll i=1; i<=n-k; i++) { ans=ans*(i+k)/i; if(ans>1e18) { return 1e18; } } return ans; }

公式化简应该没有问题，

把k变大哪怕一开始想不出来，一旦看到第一个测试样例的第一个数据，

应该就会明白了：为了更快的接近1e18

然后还有第三点，即  ans 要用128位整数来表示

稍微解释一下，

在ans快要接近1e18的时候，如果用long long表示ans，下一个数一乘，很有可能越界

然后这个越界并不是说一定就是小于0了，

可能越界完之后是一个正整数，

而且这个正整数可能比越界前小，也可能比越界前大。

所以，__int 128真是个好东西

 

AC代码：

#include<iostream> #define ll long long using namespace std; ll f(ll n,ll k) { //k+1 k+2....n //1 2 3 ...n-k __int128 ans=1; for(ll i=1; i<=n-k; i++) { ans=ans*(i+k)/i; if(ans>1e18) { return 1e18; } } return ans; } int main() { ll n,k; while(cin>>n>>k) { if(k<n/2)k=n-k; cout<<f(n,k)<<endl; } return 0; }