CF1870 F - Lazy Numbers
题意
给定 \(n,k\) ，设 \(rank_i\) 表示 \(i\) 的无前导 \(0\) 的 \(k\) 进制串在 \([1,n]\) 所有数的无前导 \(0\) 的 \(k\) 进制串中的字典序排名（从小到大）。求 \(rank_i=i,i\in [1,n]\) 的 \(i\) 的个数。
\(n,k \le 10^{18}\)
思路
如果把 \([1,n]\) 的所有数以 \(k\) 进制加入 trie 树（高位在深度低处），并钦定每个点的 \(k\) 个分支按从小到大的顺序从左往右排列。再钦定每种遍历顺序都需要从左到右（遍历不包含 trie 树的根）。那么显然某个点所代表的数一定等于这个点的 BFS 序。又由字典序的定义，可知这个点所代表的数的 \(rank\) 一定等于这个点的 DFS 序。所以我们相当于要在 trie 树上找 BFS 序等于 DFS 序的点的个数。
然后我们观察 trie 树的每一层的点，发现从左往右相邻点的 BFS 序一定增加 \(1\)，DFS 序一定增加 \(\ge 1\)，所以 DFS 序和 BFS 序的差在同一层中从左往右一定单调不减。所以我们可以对于每一层二分，找到中间存在的一段差全为 \(0\) 的区间并统计答案。
所以压力给到求一个点的 DFS 序。了解到有人这里用了数位 DP，但其实可以直接利用 trie 树的形态统计字典序小于这个点的数的个数，即为 DFS 序：
- 从 trie 树根部到这个点的链上的任意一点，它的分支（在 \([0,k)\) 中选择）只要小于它在链上所选的分支，那么这个分支的子树中的所有点都满足字典序小于我们想求 DFS 序的点，可以统计答案。
- 从 trie 树根部到这个点的链上的非根，非这个点本身的一个点一定满足字典序小于我们想求 DFS 序的点（为其前缀，且不为整个串）。
- 可以发现除了如上两种点需要被统计外，没有其他点需要被统计。
简单的说，我们可以在这个进制串后面补一些 \(0\) 使这个串的长度等于 trie 树的深度，而显然 trie 树上这个进制串形成的链的左侧的所有点都满足条件，以及本身进制串的非空前缀（长度小于这个进制串本身）所代表的点也满足条件。
所以我们可以在 \(O(\log_k{n})\) 的时间内求出一个点的 DFS 序。
在考虑上二分、枚举 trie 树每一层的循环以及多测，总的时间复杂度为 \(O(T\log_2(n)\log_k^2(n))\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define i32 int
#define i64 long long
#define i128 __int128_t
i32 T, eu, bu;
i128 n, k, ls[70], rs[70], Ans;
i128 b[70];
i128 read (){
i128 a = 0;
char c = getchar ();
while (c < '0' || c > '9')
c = getchar ();
while (c >= '0' && c <= '9'){
a = (a << 3) + (a << 1) + c - '0';
c = getchar ();
}
return a;
}
void write (i128 p){
if (p > (i128) 9)
write (p / 10);
putchar (p % 10 + '0');
}
i128 Calc (i128 x){
i128 res = 0, pre = 0;
bu = 0;
while (x > 0){
b[++ bu] = x % k;
x /= k;
}
for (i32 i = 1;i <= bu - i;++ i)
swap (b[i], b[bu - i + 1]);
for (i32 i = 1;i <= bu;++ i){
pre = pre * k + b[i];
res += min (pre, rs[i]) - ls[i] + 1;
}
for (i32 i = bu + 1;i <= eu;++ i){
pre *= k;
res += min (pre - 1, rs[i]) - ls[i] + 1;
}
return res;
}
i32 main (){
T = (i32) read ();
while (T --){
n = read ();
k = read ();
eu = 0;
Ans = (i128) 0;
for (i128 pw = 1;pw <= n;pw *= k){
++ eu;
ls[eu] = pw;
rs[eu] = min (pw * k - (i128) 1, n);
}
for (i128 i = 1;i <= eu;++ i){
i128 L, R, l0 = 0, r0 = 0, mid, res;
L = ls[i], R = rs[i];
while (L <= R){
mid = (L + R) >> 1;
res = Calc (mid) - mid;
if (res == (i128) 0)
l0 = mid;
if (res < (i128) 0)
L = mid + 1;
else
R = mid - 1;
}
if (l0 == 0)
continue;
L = ls[i], R = rs[i];
while (L <= R){
mid = (L + R) >> 1;
res = Calc (mid) - mid;
if (res == 0)
r0 = mid;
if (res > 0)
R = mid - 1;
else
L = mid + 1;
}
Ans += r0 - l0 + (i128) 1;
}
write (Ans);
puts ("");
}
return 0;
}