题解 P5634 【数码排序【加强版】】

· · 题解

题面在此

\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;
}