思路
对于一个数 $x$ 来说,它在 $K$ 进制下有 $n$ 位,分别为 $a_1,a_2,…,a_n$,$a_1$ 为低位,$a_n$ 为最高位。
设 $s_i = \sum_{i=1}^i a_i$。
首先我们可以先计算出将所有石子移动到第 $1$ 位的步数。
设 $f(i)$ 表示最终把所有石子移动到第 $i$ 位的步数,显然 $f$ 是单峰函数。
之前我们已经得到了 $f(1)$,则 $f(2) = f(1) + s_1 - (s_n - s_1)$。
得到递推式 $f(i) = f(i-1)+s_{i-1} - (s_n - s_{i-1})$。
由于 $f$ 是单峰函数,所以当 $s_{i-1}-(s_n-s_{i-1}) < 0$ 时,可以由 $i-1$ 移向 $i$,否则 $i-1$ 就是最优点。
于是得到最优解的公式为
$$f(1)+\sum_{i=2}^n min\{0, s_{i-1}-(s_n-s_{i-1})\}$$
把以上操作放在拓展为区间同时进行,用 $dfs$ 加记忆化即可,具体看代码。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int k;
int a[100];
ll f[100][10000];
ll dfs(int nw, int s, int p, bool lim) {
if (s < 0) return 0;
if (!nw) return max(0, s);
if (!lim &&~f[nw][s]) return f[nw][s];
ll ans = 0;
int up = lim ? a[nw] : k - 1;
for (int i = 0; i <= up; i ++ )
ans += dfs(nw - 1, s + ((p == 1) ? i * (nw - 1) : (nw >= p ? i : -i)), p, lim && (i == up));
if (!lim) f[nw][s] = ans;
return ans;
}
ll solve(ll x) {
int n = 0;
while (x) {
a[++ n] = x % k;
x /= k;
}
ll ans = 0;
for (int i = 1; i <= n; i ++ ) {
memset(f, -1, sizeof f);
ans += (i == 1 ? 1 : -1) * dfs(n, 0, i, 1);
}
return ans;
}
int main() {
long long l, r;
scanf("%lld%lld%d", &l, &r, &k);
printf("%lld\n", solve(r) - solve(l - 1));
return 0;
}