题解与来源题共享。已有题解默认通过；新增或编辑后需由来源域管理员审核。待审核、驳回题解仅作者和审核管理员可见。来源域：system

• 1

  CYS LV 10 MOD @ 2026-8-31 17:05:25

  1. 题目模型转换

  杨辉三角形的本质是组合数。假设行号为 $r$，列号为 $c$（均从 $0$ 开始编号），那么杨辉三角中第 $r$ 行第 $c$ 列的数字就是 $C_r^c$。

  题目要求我们将杨辉三角按行展开为一维数列，并求数字 $N$ 第一次出现的一维坐标。 根据等差数列求和公式，前 $r$ 行（第 $0$ 到第 $r-1$ 行）一共有 $\frac{r(r+1)}{2}$ 个数。 因此，第 $r$ 行第 $c$ 列的数，在展开后的一维坐标公式为：

  $$\text{Index}(r, c) = \frac{r(r+1)}{2} + c + 1$$

  我们的目标是：找到一组合法的 $(r, c)$，使得 $C_r^c = N$，并且最小化上述的 $\text{Index}(r, c)$。

  2. 核心性质与搜索范围分析

  想要高效求解，我们需要利用杨辉三角的三个核心性质来大幅缩减搜索空间。

  性质 1：对称性（只需搜索左半区）

  杨辉三角是对称的，即 $C_r^c = \binom{r}{r-c}$。 因为我们需要找的是 $N$ 第一次出现的位置，除了特殊的 $N=1$（出现在第 $0$ 行第 $0$ 列），任何数字的首次出现必定在杨辉三角的左半部分（包含正中间）。 因此，我们只搜索 $c \le \frac{r}{2}$ 的区域。转换一下不等式，即对于固定的列 $c$，合法的行号必须满足 $r \ge 2c$。

  性质 2：列数上限 $c \le 16$

  在给定的第 $c$ 列中，满足左半区条件的最顶端的数是 $C_{2c}^c$，这也是该列作为“首次出现位置”时能提供的最小值。 题目限定 $N \le 10^9$。 我们简单计算一下中间列的极值：

  • 当 $c=16$ 时，$C_{32}^{16} = 601,080,390 \le 10^9$。
  • 当 $c=17$ 时，$C_{34}^{17} = 2,333,606,220 > 10^9$。 这说明，在第 $17$ 列及更靠后的列中，能作为首次出现的最小数字都已经超过了 $23$ 亿，绝不可能等于 $N$。因此，列号 $c$ 的搜索范围被严格限制在 $[1, 16]$ 内。

  性质 3：贪心单调性（倒序搜索）

  假设存在两组不同的坐标 $(r_1, c_1)$ 和 $(r_2, c_2)$ 均满足其值为 $N$，且 $c_1 > c_2$。 因为在组合数中，固定列号时值随行号递增，既然 $c_1$ 占据了更大的列，那么它所对应的行号必然更小，即 $r_1 < r_2$。 在一维坐标公式 $\frac{r(r+1)}{2} + c + 1$ 中，行号 $r$ 的贡献是平方级的，远大于列号 $c$ 的线性贡献。因此，列号 $c$ 越大的解，其一维索引必然越小，绝对是最早出现的位置。 由此得出最优搜索策略：让 $c$ 从 $16$ 倒序遍历到 $1$，找到的第一个满足条件的解，直接输出并结束程序即可。

  3. 列内二分查找

  对于固定的列 $c$，随着行号 $r$ 的增加，$C_r^c$ 是严格单调递增的。因此我们可以在确定的上下界内通过二分查找来寻找满足 $C_r^c = N$ 的行号 $r$。

  • 二分下界 $l$：根据性质 $1$，左半区的最小行号为 $2c$。
  • 二分上界 $r$：在极端情况 $c=1$ 时，$C_N^1 = N$，因此行号最大可能达到 $N$。综合取 $\max(2c, N)$。

  4. 组合数计算

  一、 完整的数学推导

  我们的目标是：计算杨辉三角中第 $r$ 行、第 $c$ 列的数值（行列从 $0$ 开始）。根据组合数学的知识，这个值等于组合数 $C_r^c$。

  组合数的原始定义公式（基于阶乘）是：

  $$C_r^c = \frac{r!}{c!(r-c)!}$$

  如果直接用这个公式在程序里算，我们需要计算 $r!$。但 $r$ 在题目中可能大到 $10^9$，。因此，我们需要寻找一种递推关系，即：如何利用上一个状态，推导出下一个状态？

  我们先写出计算第 $i$ 项 $C_r^i$ 和它的前一项 $C_r^{i-1}$ 的公式：

  $$C_r^i = \frac{r!}{i! \times (r-i)!}$$ $$C_r^{i-1} = \frac{r!}{(i-1)! \times (r - (i-1))!} = \frac{r!}{(i-1)! \times (r-i+1)!}$$

  接下来，我们将两式相除，看看它们之间差了什么倍数：

  $$\frac{C_r^i}{C_r^{i-1}} = \frac{ \frac{r!}{i! \times (r-i)!} }{ \frac{r!}{(i-1)! \times (r-i+1)!} }$$

  使用分数的化简法则（分子乘分母的倒数），把 $r!$ 约掉：

  $$\frac{C_r^i}{C_r^{i-1}} = \frac{(i-1)! \times (r-i+1)!}{i! \times (r-i)!}$$

  接下来，利用阶乘的性质进行变形（因为 $X! = X \times (X-1)!$）：

  • $i! = i \times (i-1)!$
  • $(r-i+1)! = (r-i+1) \times (r-i)!$

  把这两个性质代入式子中，再次约分：

  $$\frac{C_r^i}{C_r^{i-1}} = \frac{(i-1)! \times (r-i+1) \times (r-i)!}{i \times (i-1)! \times (r-i)!}$$$$\frac{C_r^i}{C_r^{i-1}} = \frac{r-i+1}{i}$$

  我们将分母移到等式右边，就得到了最终递推公式：

  $$C_r^i = C_r^{i-1} \times \frac{r-i+1}{i}$$

  这个公式的含义是：第 $i$ 项的值，等于第 $i-1$ 项的值，乘以 $(r-i+1)$，再除以 $i$。

  标准代码实现 (C++)

  #include <bits/stdc++.h>
  #define ll long long
  #define mod 1000000007
  #define eps 1e-12
  using namespace std;
  
  const double PI = acos(-1);
  const int N = 2e5 + 10;
  
  // 安全递推计算组合数 C(n, m)
  ll C(ll n, ll m, ll target)
  {
  	ll res = 1;
  	for (ll i = 1; i <= m; i++)
  	{
          // 先乘后除保证不丢失精度
  		res = res * (n - i + 1) / i;
          // 如果大于目标值直接返回，既是剪枝也是为了防止后续乘法爆 long long
  		if (res > target)
  			return res;
  	}
  	return res;
  }
  
  // 根据行列坐标计算一维索引
  ll calc(ll x, ll y)
  {
  	return (1 + x) * x / 2 + y + 1;
  }
  
  void solve()
  {
  	ll n;
  	cin >> n;
      
      // 特判 n = 1，它出现在第 0 行第 0 列
  	if (n == 1)
  	{
  		cout << "1\n";
  		return;
  	}
  
      // 列数最大枚举到 16 即可，倒序搜索以保证找到的第一个解即为最早出现的位置
  	for (ll c = 16; c >= 1; c--)
  	{
          // 二分查找的上下界
  		ll l = 2 * c;
  		ll r = max(2 * c, n);
  
  		while (l <= r)
  		{
  			ll mid = (l + r) >> 1;
  			if (C(mid, c, n) == n)
  			{
                  // 找到直接输出并结束函数
  				cout << calc(mid, c) << "\n";
  				return;
  			}
  			else if (C(mid, c, n) > n)
  				r = mid - 1;
  			else
  				l = mid + 1;
  		}
  	}
  }
  
  int main()
  {
  	int _ = 1;
  	// scanf("%d", &_);
  	while (_--)
  	{
  		solve();
  	}
  
  	return 0;
  }
  

• 1