Problem

对于一个数，称将其在 $K$ 进制下合并的代价为其在 $K$ 进制下，把其各位上的数移到同一位的代价之和，将一位移到另一位上的代价为移动位数 $\times$ 移动位上的数大小。
先给定 $L,R,K$，问将 $[L,R]$ 之间所有数在 $K$ 进制下合并的最小代价。

Solution

以下称合并后有数的位置为最终位。
因为每个数的最终位都不一定相同，所以直接求解很麻烦。
我们考虑在中间拐个弯，先求出所有数合并到第 $1$ 位的代价之和。
设 $f_{p,s}$ 表示从高往低考虑到第 $p$ 位，前面的位合并到第 $1$ 位的代价为 $s$ 时所需要的总代价。
这个直接套数位 DP 记忆化搜索板子即可。
接着是要对于每个数考虑，我们还是不好确定每一个数的最终位，考虑直接暴力枚举最终位，然后数位 DP 求出对于每一个最终位，它相较于最终位为 $1$ 时可以减少的总代价，用最终位为 $1$ 时的总代价减去这些即可。
设 $g_{ed,p,s}$ 表示枚举到的最终位为 $ed$，当前从高往低考虑到第 $p$ 位，前面的位由合并到第 $1$ 位变到合并到第 $ed$ 位所减少的代价为 $s$ 的减少总代价。
于是，便解决了此题。
注意到 $ed$ 和 $p$ 的范围都是在 $10^2$ 数量级，$s$ 的范围是在 $10^3$ 数量级的，所以这样空间可能会开不下，还是把第一维去掉，每次初始化比较好。

Code

注意：以下代码将上文两部分 DP 合并为了一个 dfs。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 110, M = 2010;

int l, r, mod;
int nums[N], cnt;
int f[N][M];

int dfs(int p, int s, int end_pos, bool limit)
{
	if (s < 0) return 0;  //  s<0 时，p 必然已经在 end_pos 后面，故 s 只会继续变小，所以这里不影响正确性，同时保证了数组不会越界。
	if (!p) return max(s, 0ll);  //  s<0，反而不优。
	if (!limit && ~f[p][s]) return f[p][s];
	int up = limit ? nums[p] : mod - 1, res = 0;
	for (int i = 0; i <= up; i ++ )
		if (end_pos == 1) res += dfs(p - 1, s + i * (p - 1), 1, limit && i == up);  //  第一次 DP。
		else res += dfs(p - 1, s + ((p >= end_pos) - (p < end_pos)) * i, end_pos, limit && i == up);  //  第二次 DP，end_pos 右移，若 p>=end_pos，则移这一位的代价应减小 i；反之增加 i。
	if (!limit) f[p][s] = res;
	return res;
}

int dp(int n)
{
	cnt = 0;
	while (n) nums[ ++ cnt] = n % mod, n /= mod;
	memset(f, -1, sizeof f);
	int res = dfs(cnt, 0, 1, 1);
	for (int i = 2; i <= cnt; i ++ )
	{
		memset(f, -1, sizeof f);
		res -= dfs(cnt, 0, i, 1);  //  在最终位为 1 的基础上，减去减小代价。
	}
	return res;
}

signed main()
{
	cin >> l >> r >> mod;
	
	cout << dp(r) - dp(l - 1) << '\n';
	
	return 0;
}

by tjh:

#include <bits/stdc++.h>
#define int long long
using namespace std;
int L,R,K;
int a[100],f[100][10000];
//注：此处dfs计算石子右移改变代价计算正负相反 
int dfs(int now,int sum,int p,int lim){
    if(!now)return max(sum,0LL);//遍历到最后一位就返回答案，但如果代价增加就不移动 
    if(!lim&&~f[now][sum])return f[now][sum];//记忆化 
    int ans=0;
    int num=lim?a[now]:K-1/*K进制，不要写成9*/;
    for(int i=0;i<=num;i++)
        ans+=dfs(now-1,sum+(p==1?/*如果将石子移动到位置1则可以直接计算答案*/i*(now-1):(now<p?/*如果当前位在集合点右移一位后的左边，则代价增加，否则代价减少，因为每次只右移一位，所以只用加减i，不用乘距离*/-i:i)),p,lim&&(i==num));
    if(!lim)f[now][sum]=ans;//记忆化 
    return ans;
}
 
inline int Solve(int x){
    int n=0;
    while(x){
        a[++n]=x%K;
        x/=K;
    }
    int ans=0;
    /*
    尝试枚举所有数字的集合点 
    */
    for(int i=1;i<=n;i++){
        memset(f,-1,sizeof(f));
        if(i==1)ans+=dfs(n,0,i,1);//先将所有数字的石子集合到第1位 
        else{
            int p=dfs(n,0,i,1);//每次尝试将集合点右移一位 
            if(p<0)break;//如果移动后答案增加就不移动
            /*
            因为每次移动位于集合点左边的石子会增加，位于集合点右边的石子会减少
            而集合点右移会让位于左边的石子移动代价增加，让右边的石子移动代价减少
            所以每次移动改变的代价一定是逐渐增加的
            直到改变的代价>0就结束 
            */
            else ans-=dfs(n,0,i,1);//累加石子右移改变的代价 
        }
    }
    return ans;
}
 
signed main(){
    scanf("%lld%lld%lld",&L,&R,&K);
    printf("%lld",Solve(R)-Solve(L-1));
    return 0;
}