自动搬运

查看原文

来自洛谷，原作者为

	Pisces AFO || QwQ

搬运于2025-08-24 22:12:47，当前版本为作者最后更新于2019-11-09 16:27:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面在此

$\Large\text{大波公式警告}$

为了方便，以下我用$\lg$来代替$\log_2$

我们容易得出$ans=F(n)=F(\lfloor n/2\rfloor )+F(\lceil n/2\rceil )+n-1(n>1)$，我们令$g(n)=g(\lfloor n/2\rfloor )+g(\lceil n/2\rceil )+a(n)(n>1)$，则有$\Delta g(n)=\Delta a(n)+\Delta g(\lfloor n/2\rfloor)$

我们有恒等式$\lceil \lg2j\rceil=\lceil \lg j\rceil+1$和$\lceil \lg(2j-1)\rceil=\lceil \lg j\rceil+[j>1](j\geq1)$，所以当$a(n)=n-1$时，$\lceil \lg(n+1)\rceil$满足$\Delta f(n)=1+\Delta f(\lfloor n/2\rfloor)$

所以有结论若$F(1)=0,F(n)=F(\lfloor n/2\rfloor )+F(\lceil n/2\rceil )+n-1(n>1)$，$F(n)=\sum\limits_{k=1}^{n}\lceil \lg k\rceil$，我们就可以暴力求$F(n)$，但此时暴力仍然是$O(n)$的，因为其中有一些连续相等的数，可以考虑数论分块，复杂度大概是$O(\lg n)$的，预计得分$10\sim20pts$

令$m=\lceil \lg n\rceil$，我们考虑增加$2^m-n$项以简化运算：

$F(n)+(2^m-n)m=\sum\limits_{k=1}^{2^m}\lceil \lg k\rceil=\sum\limits_{j,k}j[j=\lceil \lg k\rceil][1\leq k\leq 2^m]=\sum\limits_{j,k}j[2^{j-1}\lt k\leq 2^j][1\leq j\leq m]=\sum\limits_{j=1}^{m}j2^{j-1}=2^m(m-1)+1$

所以我们得到$F(n)=nm-2^m+1$

但是还有一个问题：如何求$\lceil \lg n\rceil$，由于$n$太大，只能使用高精度，考虑暴力求$2^k$，暴力找到$m$，暴力取模，复杂度仍为$O(\lg n)$，预计得分仍然为$10\sim20pts$

我们有换底公式$\lg n=\log_{10}n/\log_{10}2=\log_{10}n*(1/\log_{10}2),\log_{10}n$可以用数位个数估算（偏小），$1/\log_{10}2$取估算值$3.32192809488736218170856773213$，此时就可以求得估算值$l$，考虑预处理出$2^{2^l}$，再把$l$用二进制法表示即可快速求出$2^l$，再用暴力即可（此时暴力最多算$4$次，因为$2^4\gt10$），复杂度$O(\lg \lg n)$，预计得分$100pts$，但是此题数据范围达到$10^{100000}$，必须用$FFT$优化，否则得分只能是$50\sim80pts$

（当然高精度快速幂是一样的）

但其实这道题还有个比较巧妙的理解方法：

先求式子:$f(n)=f(\lfloor n/2\rfloor )+f(\lceil n/2\rceil )+n(n>1)$，$\lfloor n/2\rfloor,\lceil n/2\rceil$取遍了$n$，如果每次加$n$，就相当于每层递归都是加$n$，一共递归了$\lceil \lg n\rceil$层，且一共递归了$n-1$次，答案就是$f(n)-(n-1)$，所以我们还是得到$F(n)=nm-2^m+1$

$Code:(part)$

int main()
{
    scanf("%s",ch);n=ch;
    int l=db*(strlen(ch)-1),ll=l;//db=3.32192809488736218170856773213
    for(register int i=1;i<=l;i<<=1,++tot)
        b[tot+1]=b[tot]*b[tot];//预处理
    while(l){
        if(l&1) s=s*b[t];//二进制分解算
        ++t,l>>=1;
    }
    while(1){//暴力算
        s+=s,++ll;
        if(s>=n) break;
    }
    T=(n%mod*ll+mod-qpow(2,ll)+1)%mod;
    T.print();
    return 0;
}