【组合数+思维+二分】杨辉三角形

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代码段

#includeusing namespace std;#define ll long longint 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=n)r=mid; else l=mid+1; } if(c(l,k)!=n)return false; else { cout<>n; for(int k=16; ;k--) { if(check(k))break; } return 0;}