Description:

第 $i$ 个人的第 $j$ 堆石子个数是 $i$ 的 $K$ 进制下的第 $j$ 位，把第 $[L,R]$ 个人的石子全部合成一堆，代价是石子数量 $\times$ 移动距离，求最小代价。

Solution:

对于每个人是相互独立的，对于每个石子一定直接移到目的地，采取这样一种合并石子的方案：先把所有石子合并到第一堆，再依次把所有石子往后移看是否更优，采用记搜 $+$ 数位 $DP$ 的方式处理。

首先是把所有石子合并到第一堆，倒序处理 $pos$ ，记 $sum$ 表示当前移动距离和了，发现对于 $sum$ 相同的状态之后的转移也相同，于是可以以 $(pos,sum)$ 为状态记忆化，注意转移过程中 $bord$ 的处理，转移时枚举下一位是什么，其实也就是把所有状态合在一起处理提高效率。

接下来处理把所有状态往后推，枚举最终汇合点，因为要求的是更改汇合点与原答案的差，所以汇合点位置变化 $1$ 每个石子会对答案产生一单位的影响，汇合点之前的往后退一格，对于当前枚举的 $i$ ，有 $i$ 个石子需要往后推，所以 $sum+=i$ ，因为 $pos$ 倒序循环，所以 $pos\ge gather$ 的要往后推，汇合点之后的距离变少了，所以 $sum -= i$ ，如果某个状态上 $sum$ 已经小于 $0$ 了，那么之后再减一定会小于零，那么可以直接 $return$ $0$ ，由于最优点一定在中位数，所以价值单调先升后降，这次 $return$ $0$ 的之后也一定不更优，所以不用管。

注意每次像普通数位 $DP$ 一样状态只保存整块，所以对于 $bord$ 特殊处理，且不更新 $f$ 数组。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll l,r;

ll k;

ll f[60][3000];

int bit[60];

ll dfs(int pos,int sum,bool bord)

{

	if(pos == 0)return sum;

	if(!bord && f[pos][sum] != -1)return f[pos][sum];

	ll res = 0;

	for(int i = 0;i <= (bord ? bit[pos] : k - 1);++i)

	{

		res += dfs(pos - 1,sum + i * (pos - 1),bord && (i == (bord ? bit[pos] : k - 1)));

	}

	if(!bord)f[pos][sum] = res;

	return res;

}

ll dfs(int pos,int sum,int gather,bool bord)

{

	if(sum < 0)return 0;

	if(pos == 0)return sum;

	if(!bord && f[pos][sum] != -1)return f[pos][sum];

	ll res = 0;

	for(int i = 0;i <= (bord ? bit[pos] : k - 1);++i)

	{

		if(pos >= gather)res += dfs(pos - 1,sum + i,gather,bord && (i == (bord ? bit[pos] : k - 1)));

		else res += dfs(pos - 1,sum - i,gather,bord && (i == (bord ? bit[pos] : k - 1)));

	}

	if(!bord)f[pos][sum] = res;

	return res;

}

ll solve(ll n)

{

	int len = 0;

	while(n > 0)

	{

		bit[++len] = n % k;

		n /= k;

	}

	memset(f,-1,sizeof(f));

	ll res = dfs(len,0,true);

	for(int i = 2;i <= len;++i)

	{

		memset(f,-1,sizeof(f));

		res -= dfs(len,0,i,true);

	} 

	return res;

}

int main()

{

	cin >> l >> r >> k;

	cout << solve(r) - solve(l - 1) << endl;

	return 0;

}