P8749 题解

Comentropy · 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) 开始。