看到数据范围就可以猜到数位dp了。显然对于一个数最后移到的位置应该是其中位数。于是考虑枚举移到的位置，那么设其左边和为l，左右边和为r，该位置数为p，则需要满足l+p>=r且r+p>=l。同时为了防止重复，枚举的应该是最左的能移到的位置，那么还需要满足l<p+r。算的时候枚举p、l、r，统计方案数，对于已固定部分直接计入，剩余部分由于每个位置都是相同的，根据距离平均值算出代价。注意讨论各种情况，非常恶心。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define ll long long#define N 66#define K 22ll l,r;int k,n,a[N];ll f[N][N*K];ll solve(ll m){ ll s=0; n=-1; while (m) a[++n]=m%k,m/=k; for (int i=n;~i;i--) { for (int y=0;y
           
            i;j--) { int l=0,r=0,t=0; for (int x=n;x>j;x--) l+=a[x],t+=a[x]*(x-j); for (int x=j-1;x>i;x--) r+=a[x],t+=a[x]*(j-x); r+=y;t+=y*(j-i);t<<=1; for (int v=max(r,l-a[j]+1);a[j]>=v-l&&v-r<=i*(k-1);v++) s+=f[i][v-r]*(t+(v-r)*(j-i+1+j)); } int l=0,t=0; for (int x=n;x>i;x--) l+=a[x],t+=a[x]*(x-i); t<<=1; for (int v=max(0,l-y+1);y>=v-l&&v<=i*(k-1);v++) s+=f[i][v]*(t+v*(1+i)); for (int j=i-1;~j;j--) { int t=0,u=0; for (int x=n;x>i;x--) u+=a[x],t+=a[x]*(x-j); u+=y,t+=y*(i-j);t<<=1; for (int p=0;p
            
             =v-l-u&&v<=j*(k-1);v++) s+=f[j][v]*f[i-j-1][l]*(t+l*(i-j)+v*(1+j)); } } } } return s>>1;}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[0][0]=1; for (int i=0;i<60;i++) for (int j=0;j<=i*(k-1);j++) if (f[i][j]&&f[i][j]<1E16) for (int x=0;x