开发笔记:[SCOI2014]方伯伯的商场之旅

#include
using namespace std;
typedef long long ll;
const int N=70;
const int M=22;
const int fix=201;
const int up=402;
ll f[N][405][2];
ll g[N][405][2];
ll L,R;
int m;
ll ansl,ansr;
int a[N],cnt;
ll wrk(){
ll ret=0;
for(int p=1;p<=cnt;p++){
for(int x=0;x){
memset(f,0,sizeof f);
memset(g,0,sizeof g);
g[cnt+1][fix][1]=1;
for(int i=cnt;i>=1;i--){
for(int j=0;j<=up;j++){
if(i==p){
if(x<a[i]){
if(g[i+1][j][0]) g[i][j][0]+=g[i+1][j][0],f[i][j][0]+=f[i+1][j][0];
if(g[i+1][j][1]) g[i][j][0]+=g[i+1][j][1],f[i][j][0]+=f[i+1][j][1];
}
else if(x==a[i]){
g[i][j][1]+=g[i+1][j][1],f[i][j][1]+=f[i+1][j][1];
g[i][j][0]+=g[i+1][j][0],f[i][j][0]+=f[i+1][j][0];
}
else{
g[i][j][0]+=g[i+1][j][0],f[i][j][0]+=f[i+1][j][0];
}
continue;
}
for(int k=0;k){
if(i>p){//before
if(j+k>up) continue;

if(k<a[i]){
g[i][j+k][0]+=g[i+1][j][0],f[i][j+k][0]+=f[i+1][j][0]+(i-p)*k*g[i+1][j][0];
g[i][j+k][0]+=g[i+1][j][1],f[i][j+k][0]+=f[i+1][j][1]+(i-p)*k*g[i+1][j][1];
}
else if(k==a[i]){
g[i][j+k][0]+=g[i+1][j][0],f[i][j+k][0]+=f[i+1][j][0]+(i-p)*k*g[i+1][j][0];
g[i][j+k][1]+=g[i+1][j][1],f[i][j+k][1]+=f[i+1][j][1]+(i-p)*k*g[i+1][j][1];
}
else{
g[i][j+k][0]+=g[i+1][j][0],f[i][j+k][0]+=f[i+1][j][0]+(i-p)*k*g[i+1][j][0];
}
}
else{//after
if(j-k<0) continue;

if(k<a[i]){
f[i][j-k][0]+=f[i+1][j][0]+g[i+1][j][0]*(p-i)*k,g[i][j-k][0]+=g[i+1][j][0];
f[i][j-k][0]+=f[i+1][j][1]+g[i+1][j][1]*(p-i)*k,g[i][j-k][0]+=g[i+1][j][1];
}
else if(k==a[i]){
f[i][j-k][0]+=f[i+1][j][0]+g[i+1][j][0]*(p-i)*k,g[i][j-k][0]+=g[i+1][j][0];
f[i][j-k][1]+=f[i+1][j][1]+g[i+1][j][1]*(p-i)*k,g[i][j-k][1]+=g[i+1][j][1];
}
else{
f[i][j-k][0]+=f[i+1][j][0]+g[i+1][j][0]*(p-i)*k,g[i][j-k][0]+=g[i+1][j][0];
}
}
}
}
}
for(int j=0;j<=up;j++){
if((fix-x<=j)&&(jfix)){
ret+=f[1][j][0]+f[1][j][1];
}
}
}
}
return ret;
}
int main(){
scanf("%lld%lld",&L,&R);
scanf("%d",&m);
L--;
cnt=0;
while(L){
a[++cnt]=L%m;
L/=m;
}
if(cnt==0){
ansl=0;
}
else{
ansl=wrk();
}

cnt=0;
while(R){
a[++cnt]=R%m;
R/=m;
}
ansr=wrk();
printf("%lld",ansr-ansl);
}