看到数据范围就可以猜到数位dp了。显然对于一个数最后移到的位置应该是其中位数。于是考虑枚举移到的位置，那么设其左边和为l，左右边和为r，该位置数为p，则需要满足l+p>=r且r+p>=l。同时为了防止重复，枚举的应该是最左的能移到的位置，那么还需要满足l<p+r。算的时候枚举p、l、r，统计方案数，对于已固定部分直接计入，剩余部分由于每个位置都是相同的，根据距离平均值算出代价。注意讨论各种情况，非常恶心。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define ll long long
#define N 66
#define K 22
ll l,r;
int k,n,a[N];
ll f[N][N*K];
ll solve(ll m)
{
ll s=;
n=-;
while (m) a[++n]=m%k,m/=k;
for (int i=n;~i;i--)
{
for (int y=;y<a[i];y++)
{
for (int j=n;j>i;j--)
{
int l=,r=,t=;
for (int x=n;x>j;x--) l+=a[x],t+=a[x]*(x-j);
for (int x=j-;x>i;x--) r+=a[x],t+=a[x]*(j-x);
r+=y;t+=y*(j-i);t<<=;
for (int v=max(r,l-a[j]+);a[j]>=v-l&&v-r<=i*(k-);v++)
s+=f[i][v-r]*(t+(v-r)*(j-i++j));
}
int l=,t=;
for (int x=n;x>i;x--) l+=a[x],t+=a[x]*(x-i);
t<<=;
for (int v=max(,l-y+);y>=v-l&&v<=i*(k-);v++)
s+=f[i][v]*(t+v*(+i));
for (int j=i-;~j;j--)
{
int t=,u=;
for (int x=n;x>i;x--) u+=a[x],t+=a[x]*(x-j);
u+=y,t+=y*(i-j);t<<=;
for (int p=;p<k;p++)
{
for (int l=;l<=(i-j-)*(k-);l++)
for (int v=max(,l+u-p+);p>=v-l-u&&v<=j*(k-);v++)
s+=f[j][v]*f[i-j-][l]*(t+l*(i-j)+v*(+j));
}
}
}
}
return s>>;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj3598.in","r",stdin);
freopen("bzoj3598.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
cin>>l>>r>>k;
f[][]=;
for (int i=;i<;i++)
for (int j=;j<=i*(k-);j++)
if (f[i][j]&&f[i][j]<1E16)
for (int x=;x<k;x++)
f[i+][j+x]+=f[i][j];
cout<<solve(r+)-solve(l);
return ;
}