【洛谷 P8749】[蓝桥杯 2021 省 B] 杨辉三角形 题解（动态规划+组合数学+滚动数组）

[蓝桥杯 2021 省 B] 杨辉三角形

题目描述

下面���图形是著名的杨辉三角形:

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 1 , … 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1, \ldots 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…

给定一个正整数 N N N，请你输出数列中第一次出现 N N N 是在第几个数。

输入格式

输入一个整数 N N N 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

6

样例输出 #1

13

提示

对于 20 % 20 \% 20% 的评测用例, 1 ≤ N ≤ 10 1 \leq N \leq 10 1≤N≤10;

对于所有评测用例, 1 ≤ N ≤ 1 0 9 1 \leq N \leq 10^9 1≤N≤109 。

蓝桥杯 2021 第一轮省赛 B 组 H 题。

---

思路

首先，从输入中读取一个整数n。如果n等于1，直接输出1并结束程序。

然后，进入一个最大迭代次数为1e5的循环，每次循环的索引为i。在每次循环中，首先计算一个变量t，它等于i模2的结果，用于实现动态规划数组的滚动更新。

接下来，初始化动态规划二维数组dp的当前行的第一个元素为1。然后，进入一个最大迭代次数为i的循环，每次循环的索引为j。在这个循环中，更新dp数组的当前行的第j个元素，它等于上一行的第j-1个元素和第j个元素之和，这就是杨辉三角形的特性。

如果计算出的组合数大于10的9次方，就跳出内部循环，因为题目中给出的n的最大值是10的9次方。

如果n等于dp数组的当前行的第j个元素，那么就找到了n在杨辉三角形中的位置。此时，计算出n的位置，使用的是等差数列求和的公式。然后，输出结果并结束程序。

如果在所有的循环中都没有找到n，那么最后，再次使用等差数列求和的公式，计算出n的位置，然后输出结果。

注意

1. 在计算位置时，要将乘法结果强制转换为 long long 类型，否则无法通过部分测试点。
2. 动态规划的 j 是从1开始的，会把数字 1 1 1的判断漏掉。数字 1 1 1第一次在数列中出现的位置一定是1。如果n等于1，直接输出1并结束程序。

   if (n == 1) {cout ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin  n;if (n == 1) {cout int t = i & 1;dp[t][0] = 1;for (int j = 1; j // 求组合数dp[t][j] = dp[t ^ 1][j - 1] + dp[t ^ 1][j];if (dp[t][j]  1e9) {break;}if (n == dp[t][j]) {// 等差数列求和cout