似乎做出来之后很简单了
显然对于每一个数都是在带权中点最优
假设先把所有数都移到最后一位
再枚举有多少能往左移更优
考虑显然在找中点的时候能往左移的条件是当前位置前缀大于后缀
而前后缀之差的范围是很小的，可以直接作为状态维护
统计出所有更优的状态减一下就是了
具体看代码吧
我tm在口胡什么啊（逃）
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
char ch=getchar();
int res=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
return res;
}
const int N=70,M=4006;
int l,r,k,dig[70],tot,n,f[N][M];
int dfs1(int pos,int val,int lim){
if(!pos)return val;
if(!lim&&f[pos][val]!=-1)return f[pos][val];
int mx=lim?dig[pos]:k-1,res=0;
for(int i=0;i<=mx;i++){
res+=dfs1(pos-1,val+i*(pos-1),lim&(i==dig[pos]));
}
if(!lim)f[pos][val]=res;return res;
}
int dfs2(int pos,int val,int to,int lim){
if(val<0)return 0;
if(!pos)return val;
if(!lim&&f[pos][val]!=-1)return f[pos][val];
int mx=lim?dig[pos]:k-1,res=0;
for(int i=0;i<=mx;i++){
if(pos>=to)res+=dfs2(pos-1,val+i,to,lim&(i==dig[pos]));
else res+=dfs2(pos-1,val-i,to,lim&(i==dig[pos]));
}
if(!lim)f[pos][val]=res;return res;
}
inline int solve(int x){
tot=0;
while(x){
dig[++tot]=x%k;
x/=k;
}
memset(f,-1,sizeof(f));
int res=dfs1(tot,0,1);
for(int i=2;i<=tot;i++){
memset(f,-1,sizeof(f));
res-=dfs2(tot,0,i,1);
}
return res;
}
signed main(){
l=read(),r=read(),k=read();
cout<<(solve(r)-solve(l-1))<<'
';
}