[C++知识库]【组合数+思维+二分】杨辉三角形

题目

3418. 杨辉三角形 - AcWing题库?

解释

• 每一行左右两半都是重复的，所以直接考虑左半部分
• 
• 对于每一行i每一列j的值可以用组合数C(i，j)表示
• 数据范围不超过1e9,而C(34, 17) > 1e9, C(32, 16) < 1e9
• 因此对于C(a,b)，b不会超过16
• 又因为随意框选出来一个三角形，可以发现最下角的数一定是最大的
• 且从该图可以看出对于每一行最后一个元素（可以近似看成一列）从上到下是单调递增的
• 所以固定b，对a进行二分查找，最下角是C(2*b,b)因此l=2*k,r=n

代码段

#include<iostream>
using namespace std;
#define ll long long
int n;
ll c(int a,int b)
{
    ll res=1;
    for(int i=a,j=1;j<=b;i--,j++)
    {
        res=res*i/j;
        if(res>n)return res;
    }
    return res;
}
bool check(int k)
{
    ll l=2*k,r=n;
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(c(mid,k)>=n)r=mid;
        else
        l=mid+1;
    }
    if(c(l,k)!=n)return false;
    else
    {
        cout<<l*(l+1)/2+k+1<<endl;
            return true;
    }
}
int main()
{
    cin>>n;
    for(int k=16; ;k--)
    {
       if(check(k))break;
    }
    return 0;
}