自动搬运

查看原文

来自洛谷，原作者为

	Comentropy 思绪的风雨，吹起遥远的回忆...

搬运于2025-08-24 22:42:04，当前版本为作者最后更新于2022-12-27 19:03:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

杨辉三角

本题需要运用杨辉三角的性质，建议先学习 （尽管可能用不上）。杨辉三角是数列的相关知识，其拥有一定性质，如对称性和通项。这些性质可以帮助我们解题。

分析

首先对题面做分析。

• 暴力是可以稳稳 $20pts$ 的。
• 对 $10^9$ 的数据量，程序必须拥有 $n^{ \frac{1}{2} }$ 级别及以下的复杂度，常数要求没有那么严格。

那么这道题可以利用杨辉三角的性质：分析的时候可以利用对称性简化分析（其实没有必要）。并发现有如下性质：按照对角线顺序分析，在原图第 $n$ 行，且位于第 $m$ 条对角线上的数，为 $C_{n}^{m}$，如图（图中的 $n$ 指的是层数减一）。

（该图有误，见后方纠正）。

按对角线顺序遍历，可以利用单调性进行二分。

那么从哪条对角线开始遍历呢？观察这些对角线方向的数，其起始元素为 $C_{2k}^{k}$，只需找到最小的 $k$ 使得 $C_{2(k+1)}^{k+1}> n_{max}=10^9$ 即可，原因易知（不懂见 ps ）。计算可知 $k=16$。

已知一个数所在的对角线和行数，其位置容易求得，不再赘述。

复杂度是 $\Theta(\log n)$ 级别的，常数在 $16$ 左右。

ps: 原因是每个斜行（对角线方向）都具有单调性，若一个斜行开头的数比 $n$ 大，则答案一定不在该斜行中。

Code

#include<cstdio>
typedef long long LL;
const LL INF=1e9;
LL n;
LL C(LL a,LL b){
    LL res=1;
    for(LL i=a,j=1;j<=b;i--,j++){
        res=res*i/j;
        if(res>n)	// fixed
            return res;
    }
	return res;
}
int main(){
    scanf("%lld",&n);
    // 只需遍历 16 行
    if(n==1){
        printf("1");
        return 0;
    }
    for(int i=16;i>=0;i--){
        LL l=2*i,r=INF,mid,lim;
        while(l<=r){
            mid=(l+r)>>1,lim=C(mid,i);
            if(lim==n){
                printf("%lld",(mid+1)*mid/2+i+1);
                return 0;
            }else if(lim<n)
                l=mid+1;
            else{
                r=mid-1;
            }
        }
    }
    return 0;
}

Update

• 2023/2/3：本题在进行组合数计算时需要防止溢出，而二分只需要知道大小结果，故应当在计算中添加一行：

if(res>n)	return res;

特此感谢评论区的 hack 数据：

input: 71523144
output: 4956

• 2024/4/1 勘误：感谢评论区的纠正，图中的组合数应从 $C(n,0)$ 开始。