题目

在这里插入图片描述
可以结合目录来理解文章~

原始方法

这个方法可以拿到40分。N数值比较大的时候，运行时间会超过限制。

思路

逐行生成杨辉三角，找到了需要的N以后就停止循环，并输出对应的位置。

变量解释

用于计算N的位置的公式如下：

pos = (1 + i)*i/2 + j

其中，i是从0开始的，代表N所在的行。j是从0开始的，代表N在所在行的位置（注意，由于每行行首会有一个用来占位的"0"，因此也可以认为j是从1开始的）。

优化技巧

在基本思路的基础上，用到了两个优化存储的技巧。

杨辉三角只保留程序运行到的行。

previous_line和new_line交替存储，这样就不必保存对解题无用的、太过久远的行。

将杨辉三角保留一半。

由于杨辉三角是对称的，每行只保留前一半以节约空间。计算时，需要考虑奇数行和偶数行的影响。

完整代码

# Boundary test!
n = int(input())'''
将杨辉三角保留一半，以节省空间和时间
'''# 初始化第一行
previous_line = [0,1]i = 0 # 标记当前行
is_odd = -1 # 标记旧行是否为奇数行，第0行是偶数行，故初始化为-1while(True):# 取出旧行previous_line = previous_line# 计算新行new_line = [0] # 保持新行第一个为0for k in range(len(previous_line)-1):new_line.append(previous_line[k] + previous_line[k+1])if is_odd == 1:new_line.append(2*previous_line[-1])# 标记所需元素在新行的位置i = i + 1 # 标记新行is_odd = -is_odd # 标记新行是否为奇数行if n in new_line:j = new_line.index(n) break # 将计算得到的新行置为旧行previous_line = new_linepos = (1 + i)*i/2 + jif n == 1:print(1)
else:print(int(pos))

满分方法

基本复刻了下面这个博客的代码和思想：

第十二届蓝桥杯B组C/C++省赛—H题（杨辉三角）_思维题_萌小帝的博客-CSDN博客

下文是我对这个方法的理解，可能会有一些地方说的不够清楚，推荐和大佬的原文比对着看（不过我有些标记和原文不一样，得注意一下）。如果有错误希望大家可以帮忙指正。

前言

这份代码能过洛谷的评测，在蓝桥杯系统里只有70分，，，明明自己测的所有特殊值都是对的，调了很久还是放弃了。如果有大佬能告诉我为什么过不了蓝桥杯我将感激不尽。

思路

这个方法可以概括为斜行查找。

斜行的含义

由于杨辉三角的对称性，可以只保留左半部分进行考虑。

在这里插入图片描述

也就是这样：

在这里插入图片描述

斜行的引入

通过图，我们可以发现通过行和列的枚举是不好的，看数据1e9也就是十亿，这是个很大的工程，因此我们试想可不可以从斜行来观察呢？

绘制示意图，图中的蓝色箭头标明了斜行的走向。

在这里插入图片描述

为了表达清楚，将杨辉三角原来的行称为标准行。标准行和斜行都是从0开始的。

观察每个斜行的首元素，可以得到：第0斜行的首元素为C(0,0)，第1斜行为C(1,2)，第2斜行为C(2,4)，第3斜行为C(3,6)…
求每个斜行的首元素的通项，易得：若当前为第i个斜行，则该斜行首元素为C(i,2i)。

考虑杨辉三角和二项式系数的关系：

杨辉三角，是二项式系数C(n,m)在三角形中的一种几何排列。

对应本题，C(n,m)中的n对应于斜行的行数，m对应于标准行的行数。 这个概念是之后解题的重要依据。

枚举的思路

从第16斜行开始向前枚举。在斜行中查找n，出现等于n的数直接返回位置。
对于查找，由于斜行元素是单调递增的，因此可以对每个斜行采用二分的方法查找n。
对于位置，可以在查找的时候确定。遍历得到n所在标准行r和所在斜行k ，通过等差数列求和公式 r*(r+1)/2计算n之前所有标准行的元素个数再加k+1。

加粗内容的补充解释：

为什么从第16斜行开始？

题目给定的n最大到1000000000。C(17,34)=2333606220，是斜行首元素第一次大于1000000000（1e9），由于每个斜行内的元素是单调递增的，因此17斜行的每一个值都必定大于1e9。又由于每个斜行的首元素也是单调递增的，因此17斜行之后的所有斜行的所有元素都是大于1e9的。

因此，只需要考虑前16斜行即可。
为什么向前枚举时找到的第一个n就是杨辉三角中第一次出现的n？

等价于证明：若第i和第i+j个斜行中都出现了n，则第i+j个斜行中的n一定出现在第i个斜行中的n之前。

以n=6为例：

画个图可以比较直观的解释这个问题。

考虑第1个斜行出现的6。可以看到，红色区域全是大于6的值，也就是说，6不可能在这一区域出现。若有6在第1个斜行之后的斜行出现，则必然是在这个6之前的。

在这里插入图片描述

斜行内的元素的通项是什么？

考虑杨辉三角和二项式系数C(n,m)的关系，元素在斜行中每向前一步，对应标准行向下一行。因此，第k个斜行第一个元素为C(k,2k)，第二个元素就是C(k,2k+1)，依次类推。

代码

# Boundary test!
# n = int(input())'''
斜行查找
'''
import sys
# ====================
# 求解组合数C的函数
# ====================
def C(a, b):top = 1bot = 1i = bfor j in range(1, a+1):top *= ibot *= ji -= 1return top//bot# ====================
# 对第k个斜行进行二分查找的函数
# ====================
def bi_search(k):l = 2*kr = max(n, l)while r > l: # l是偏小的，r是偏大的mid = (l + r)//2median = C(k, mid)if median == n: breakelif median > n:r = mid - 1else:l = mid + 1# 没找到n，继续遍历if C(k, r) != n:return False# 找到n，输出位置print((1 + r)*r//2 + k + 1)return True# ====================
# 程序主体
# ====================    
n = int(input())# 如果是1，直接输出
if n == 1:print(int(1))sys.exit()# 向前枚举
for i in range(0, 16):k = int(16 - i)# 找到n就跳出来if bi_search(k):break