3418. 杨辉三角形 - AcWing题库
题目描述:
思路：
从上图片中，我们可以看出来这是一个对称图形，所以我们只看左半部分就可以了，我们一行一列去做数据量是1e9这样会很麻烦，所以我们这里做一个思想转换，斜着看，也就是斜行。
如上面图片：
1、我们可以发现每一个斜行越往下的方向是递增的
2、 开始的数字是C的底数是上面的2呗也就是------>C（k，2k）
3、无论横着按行去看还是竖着按列去看，还是斜行去看都是最里面的数是大的，也就是2， 6，20这一列是大的，所以也就是越靠下的斜行，数越大，所以我们再找N的时候，就 要 从下去开始找，这也是为什么后面在代码部分会从后往前去遍历。
4、然后根据数据范围我们可以知道 N最大1e9，C(34, 17) > 1e9, C(32, 16) < 1e9，因此只要枚举前16个斜行即可
AC代码：
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int n;
ll C(int a,int b)
{
ll res = 1;
// C(a, b) = a!/b!(a-b)! = a * (a-1) .. (a-b)个 / b!
for(int i=a,j=1;j<=b;j++,i--)
{
res = res * i / j;
//防爆 ll ，res大了也没用 最多1e9
if(res > n) return res;
}
return res;
}
//二分
bool check(int k)
{
//这里虽然我们是从斜行枚举，但是我们实际是从第16行开始，往上走
ll l = 2 * k,r = max(n,2*k);
while(l < r) //左模板
{
int mid = l + r >> 1;
if(C(mid,k) >= n) r = mid;
else l = mid + 1;
}
//如果没找到 返回false
if(C(l,k) != n) return false;
//等差数列求和公式
cout << r*(r+1) / 2 + k + 1 << endl;
return true;
}
int main()
{
cin >> n;
//从第十六行开始枚举
for(int k = 16;;k--)
{
if(check(k)) break;
}
return 0;
}代码部分讲解：
为什么左边界为什么是2k？（也是为什么k不能从0开始枚举）
2k和n都是行号。假如我们要找n这个数，我们一定可以在第n行的第1个数找到，也就是C（n,1），但是这个n可能不是第一个出现的n。例如杨辉三角里面的6这个数，它在（6,1）和（4,2）均出现了，要找第一个出现的6，应该是（4,2）这个。
每个斜行的起点的行号是2k,终点是n。而起点的值是C(2k,k)，终点的值是C(n,k)我们要在[2k,n]在这个区间内找到等于n的值
为什么max（n,2*k）？
当n=1时，k从16往下检查时，当k=1时，l=2k,r=n=1,因为l>r，会直接跳出二分的while循环
C（r,k）=C（1,1）=1。根据C（1,1）得到的顺序值，此时就会输出1的位置是3，但是这个位置不是第一次出现的位置。正确的位置应该是(0,0)
最后求顺序值的时候 (r + 1) * r / 2 + k + 1 到底怎么来的?
根据等差数列，第一行是1个数，第二行是二个数，第三行是3个数，依次类推，等差数列求和公式Sn = （首项+末项）*项数 / 2
当为C(4,2) == 6时，r = 4，k = 2，它的前面有4行，前面4行的总个数为1 + 2 + 3 + 4= 10，也就是 (r + 1) * r / 2，再加上它在这行的位置k + 1
欢迎不会的小伙伴留言~
