题目描述 从杨辉三角中按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,... 给定一个正整数N，求数列中第一次出现N是第几个数。 输入格式 输入一个整数N。 输出格式 输出一个整数代表答案。 数据范围 1≤N≤10^10 样例 输入样例： 6 输出样例： 13给出C++优化代码和详细注释

解题思路：
我们发现其实我们无法计算整个数列，因为其规模太大，所以需要寻找特殊的规律进行计算
我们尝试将杨辉三角转化成如下的形式：
1
1,1
1,2,1
1,3,3,1
1,4,6,4,1
可以发现一个规律，即每一行前后均为1，并且每一行的元素可以由上一行相邻的两个元素和组成。如果我们将每个数都减去其前面的元素，我们能够得到如下形式的数列：
1,0,1,0,2,0,1,0,3,0,3,0,1,0,4,...
可以发现，每当出现一个新的数n时，一定伴随着一个0的出现。
现在对于每个数列的位置pos，我们都能够通过pos / (pos的行数)得到其所在行的位置k，然后我们再通过pos % (pos的行数)得到其在该行中的位置j。这样就可以使用组合数快速计算出其对应的数值了。
具体地，对于pos所在的行，我们使用二项式系数计算其对应的系数，即C(k, j)。由于杨辉三角、下三角和正方形三个部分组成的三角形是关于竖直中线和左下到右上的中线对称的，所以当k > j时，我们可以将其替换为C(k, k - j)。
而对于每次出现新的数n，我们都能够找到其对应的位置pos，根据已知规律计算出其值即可。
注意，由于N可能很大，我们需要使用long long存储计算结果。
时间复杂度 分别为：计算0~pos范围内的所有数字时间复杂度为O(pos * log(pos))，pos的计算时间复杂度为O(log(N))，因此总的时间复杂度为O(pos * log(pos) + log(N))。

C++ 代码

相关问题

题目描述 下面的图形是著名的杨辉三角形： 如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \cdots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯ 给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？ 输入描述 输入一个整数 NN。 输出描述 输出一个整数代表答案。

算法1 数学

数列中的数可以通过组合数来计算：第 n 行第 k 个数为 C(n-1, k-1)。因此可以按顺序计算数列中每个数，直到第一个大于等于 N 的数出现为止。

时间复杂度：O(N^2)

C++ 代码

算法2 二分查找

观察数列，可以发现它是逐行递增的，因此可以考虑使用二分查找。具体地，在数列中找到第一个大于等于 N 的数。至于如何找到第 n 行第 k 个数，可以使用公式 C(n-1, k-1)，也可以使用递推式 C(n, k)=C(n-1, k-1)+C(n-1, k)来计算。

时间复杂度：O(log^2 N)

C++ 代码

杨辉三角问题，如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \cdots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯ 给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？ 输入描述 输入一个整数 NN。 输出描述 输出一个整数代表答案。 输入输出样例 示例 1 输入 6 copy 输出 13 copy 评测用例规模与约定 对于 20%20​​ 的评测用例，1\leq N\leq 101≤N≤10​； 对于所有评测用例，1\leq N\leq 10000000001≤N≤1000000000。请给出思路

题目大意

给定一个正整数 N，按照杨辉三角的顺序将其中所有的数依次排列成一行，求第一次出现 N 的位置。

思路分析

首先我们需要知道杨辉三角的性质，即第 n 行有 n 个数，每行的两端数为 1，第 n 行的第 m 个数等于第 n-1 行的第 m-1 个数加上第 m 个数，即：

$$C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}$$

杨辉三角规律图

根据以上杨辉三角的规律，我们可以生成杨辉三角，并且也可以找出第一次出现 N 的位置。具体做法如下：

- 生成杨辉三角。我们可以使用二维数组来存储杨辉三角，其中第 i 行第 j 列的值表示杨辉三角中第 i 行第 j 列的数。
- 遍历杨辉三角，找到第一次出现 N 的位置并记录。我们可以从第一行第一列开始遍历，如果当前数字等于 N，则记录该数字的位置即可。

代码实现