P8749（杨辉三角）

· · 个人记录

做题笔记

该题使用到了组合数的O（n）级别计算方法，还有杨辉三角的相关性质。

杨辉三角的性质如下：

杨辉三角有 第0层， 所以第n层，与第n行含义不同 第n行 为第n-1 层，下面结论 要分辨 行与层

第0层 1

第1层 1 1

第2层 1 2 1

第3层 1 3 3 1

第4层 1 4 6 4 1

第5层 1 5 10 10 5 1

第6层 1 6 15 20 15 6 1

第7层 1 7 21 35 35 21 7 1

第8层 1 8 28 56 70 56 28 8 1

第9层 1 9 36 84 126 126 84 36 9 1

每一层对应元素为

C(n,0) C(n,1).....C(n,n-1) C(n,n);

根据数位于的层数和对角线数可以计算数是第几个。

例如：C(n,m) 就是位于第n层第m个对角线的数， (n+1)*n/2+m+1就是该数字对应的位置。

每一个对角线开头的元素都符合C(2k,k)条件，且对角线上，后面的数一定大于前面的数。注：k为任意常数。

本题中的数据最大为10^9，C（32,16）已经大于10^9，所以下面的代码中我们只需要枚举0—16即可。

AC代码如下：

#include<iostream>
using namespace std;
typedef long long LL;
int n;
LL C(LL a,LL b)//计算组合数的值
{
    LL ans=1;
    for(int i=1;i<=b;i++)
    {
        ans=ans*(a-b+i)/i;
        if(ans>n)return ans;//题目特殊只需知道ans和n的大小关系就行
    }
    return ans;
}
int main()
{
    cin>>n;
    if(n==1)
    {
        printf("1");
        return 0;
    }
    for(int i=16;i>=0;i--)
    {
        if(C(2*i,i)<=n)//遍历对角线的开头，因为后面的数一定比开头大
        {
            LL mid,l=i,r=1000000005;
            while(l<r)//二分查找该对角线下的对应答案；
            {
                mid=(l+r+1)>>1;
                LL t=C(mid,i);
                if(t==n)
                {
                    printf("%lld",(mid+1)*mid/2+i+1);//计算第mid层，第i条对角线数据是第几个；
                                                     //需要注意的是杨辉三角最上层是第0层；
                    return 0;
                }
                else if(n>t)l=mid;
                else r=mid-1;
            }
        }
    }
    return 0;
}