ReMind

Recent Writing

See 247 more →

杨辉三角形_(数论规律，组合数)

3 min read

原题链接：3418. 杨辉三角形 - AcWing题库

题意：杨辉三角形中，找到一个数 N 第一次出现的位置

思路

这是一道找规律的题

  • 首先杨辉三角形是对称的，找第一次出现的数只看左半边就可以

  • 一行一行看是遍历的思想，如果暴力做时间肯定超，可以斜着看，以每一斜行为基本的查找单位

  • 对于每次查找，可以看到每行最大值在中间，即 处，可以先找这个位置，且从下往上找，因为如果找到了等于 N 的数，那么对于同横行，其他数所在的斜行中要是存在一个数为N，那么一定是在更深的横行中

  • 组合数很大，找一个范围在 的数不会找太深，可以看到 ，只需要找16斜行就可以了

  • 每一斜行是递增的，可以用二分查找加快查找速度

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
typedef long long LL;
 
int n;
 
LL C(int a, int b)
{
    LL ans = 1;
    for(int i = a, j = 1; j <= b; i --, j ++)
    {
        ans = ans * i / j;
        if(ans > n) break;
    }
    
    return ans;
}
 
bool check(LL x)
{
    LL l = 2 * x, r = n;
    
    if(l >= r) return false;
    
    while(l < r)
    {
        int mid = l + r >> 1;
        if(C(mid, x) >= n) r = mid;
        else l = mid + 1;
    }
    
    if(C(r, x) != n) return false;
    else
    {
        cout << r * (r + 1) / 2 + x + 1 << endl;
    }
}
 
 
int main()
{
    cin >> n;
    
    for(int i = 16; ; i --)
    {
        if(check(i))
            break;
    }
    
    return 0;
}

注意到杨辉三角起始是 0，所以坐标位置要从 0 开始计数

Graph View