[CF1870F] Lazy Numbers

Lazy Numbers
我觉得本题难度在于银剑的构造......
我们把 k 进制下的数去掉前导零放在 Trie 树上,并且越高位的深度越小,这样我们看出某个节点的 dfs 序就是排名,称排名减数值为 va。我们需要求 va=0 的点数。

不难发现某一深度从左往右的 va 单调不降,所以可以二分求出每层的点数。

然后求 dfs 序可以手玩,于是就没了。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll __int128_t
const int UP=65;
int T,dep;
ll n,k,LL[UP],RR[UP],b[UP],Ans;
ll read(){
    ll x=0;
    char s=getchar();
    while(s<'0'||s>'9'){
    	s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);
		s=getchar();
	}
	return x;
}
void prt(ll va){
    if(va>(ll)9) prt(va/10);
    putchar(va%10+'0');
}
ll calc(ll x){
    ll res=0,tmp=0;int de=0;
    while(x){b[++de]=x%k;x/=k;}
    for(int i=1;i<=de/2;i++) swap(b[i],b[de-i+1]);
    for(int i=1;i<=de;i++){
        tmp=tmp*k+b[i];
        res+=min(tmp,RR[i])-LL[i]+1;
    }
    for(int i=de+1;i<=dep;i++){
        tmp*=k;
        res+=min(tmp-1,RR[i])-LL[i]+1;
    }
    return res;
}
int main (){
    T=(int)read();
    while (T--){
        n=read();k=read();dep=0;
        Ans=(ll)0;
        for(ll va=1;va<=n;va*=k){
        	dep++;
            LL[dep]=va;RR[dep]=min(va*k-(ll)1,n);
        }
        ll mid,res,res1,res2,L,R;
        for (ll i=1;i<=dep;i++){
            L=LL[i];R=RR[i];
            res1=0;res2=0;
            while(L<=R){
                mid=(L+R)>>(ll)1;
                res=calc(mid)-mid;
                if(res==(ll)0) res1=mid;
                if(res<(ll)0) L=mid+1;
                else R=mid-1;
            }
            if(res1==(ll)0) continue;
            L=LL[i];R=RR[i];
            while (L<=R){
                mid=(L+R)>>(ll)1;
                res=calc(mid)-mid;
                if(res==(ll)0) res2=mid;
                if(res>(ll)0) R=mid-1;
                else L=mid+1;
            }
            Ans+=res2-res1+(ll)1;
        }
        prt(Ans);printf("\n");
    }
    return 0;
}