蓝桥杯历届真题 杨辉三角形【第十二届】【省赛】【B组】

题目大意
将杨辉三角形按照从上到下、从左至右的顺序排成一个数列。输入一个正整数$N$，请你判断该数列中第一次出现$N$是数列中第几个数。
解题思路

• 思路一

  $找规律$
       $1$
       $1$  $1$
       $1$  $2$  $1$
       $1$  $3$  $3$  $1$
       $1$  $4$  $6$  $4$  $1$
       $1$  $5$  $10$  $10$  $5$  $1$

• 思路二
  $二分+组合数$

1. 根据杨辉三角形与组合数的联系，第$i$行第$j$列的数都是组合数$C(i,j)$，因为$C(n,1)=n$，所以对于每个输入的$n$必定有解。

2. 由于杨辉三角形是左右对称的，且数列是按照每行从左到右排列的，所以数字第一次出现必定在左边。
          $1$
         $1$ 
        $1$ 2
       $1$ 3
      $1$ 4 6
     $1$ 5 10
    $1$ 6 15 20

3. 根据题意$n$最大$1e9$，且$C(34,17)>1e9$，$C(32,16)<1e9$，因此只要枚举前$16$个斜行即可

4. 观察上面三角形可以看出，除了第一条边，一条边上的数都是严格单调递增的，所以我们可以对每一条边进行一次二分操作

5. 组合数计算需要用数学公式$C(n,m)=\frac{n!}{(n-m)!\ast m!}=\frac{(n-m+1)(n-m+2)\ast \dots \ast n}{1\ast 2\ast \dots \ast m}$直接算，如果数组的话会超内存。
   附上代码

   #pragma GCC optimize("-Ofast","-funroll-all-loops")
   #include<bits/stdc++.h>
   #define int long long
   #define lowbit(x) (x &(-x))
   #define endl '\n'
   #define debug(x) cout<<"# "<<x<<endl;
   using namespace std;
   const int INF=0x3f3f3f3f3f3f3f3f;
   const int dir[4][2]={-1,0,1,0,0,-1,0,1};
   const double PI=acos(-1.0);
   const double e=exp(1.0);
   const double eps=1e-10;
   const int M=1e9+7;
   const int N=2e3+10;
   typedef long long ll;
   typedef pair<int,int> PII;
   typedef unsigned long long ull;
   int C(int a,int b,int n){
   	int ans=1;
   	for(int i=a,j=1;j<=b;i--,j++){
   		ans=ans*i/j;
   		if(ans>n) return ans;
   	}
   	return ans;
   }
   bool check(int k,int n){
   	int l=2*k,r=max(n,l);
   	while(l<r){
   		int mid=(l+r)/2;
   		if(C(mid,k,n)>=n) r=mid;
   		else l=mid+1;
   	}
   	if(C(r,k,n)!=n) return false;
   	cout<<(r+1)*r/2+k+1<<endl;
   	return true;
   }
   signed main(){
   	ios::sync_with_stdio(false);
   	cin.tie(0);cout.tie(0);
   
   	int n;
   	cin>>n;
   	for(int i=16;i>=0;i--){
   		if(check(i,n)) break;
   	}
   	return 0;
   }