题解 P5626 【【AFOI-19】数码排序】

· · 题解

这其实也是原题，很早以前出公开赛准备用这个，只不过数据强太多了...不说了，上题解（加强版在此）

为了方便，以下我用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 lgj\rceil+1和\lceil lg(2j-1)\rceil=\lceil lgj\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 lgk\rceil，我们就可以暴力求F(n)，但此时暴力仍然是O(n)的，因为其中有一些连续相等的数，可以考虑数论分块，复杂度大概是O(lgn)的，在我的那道题中预计得分10\sim20pts

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

F(n)+(2^m-n)m=\sum\limits_{k=1}^{2^m}\lceil lgk\rceil=\sum\limits_{j,k}j[j=\lceil lgk\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 lgn\rceil，由于n太大，只能使用高精度，考虑暴力求2^k，暴力找到m，暴力取模，复杂度仍为O(lgn)，在我的那道题中预计得分仍然为10\sim20pts

我们有换底公式lgn=\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(lglgn)，预计得分100pts，但是此题数据范围达到10^{100000}，必须用FFT优化，否则得分只能是50\sim80pts（均指在我的那道题中）

另外，提供本题（较弱版的AC代码）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int qpow(int a,int b){
    int s=1;
    while(b){
        if(b&1) s*=a;
        a*=a,b>>=1;
    }
    return s;
}
signed main(){
    int n,m;
    cin>>n;m=ceil(log2(n));
    cout<<m*n-qpow(2,m)+1;
    return 0;
}