bzoj 3598 [ Scoi 2014 ] 方伯伯的商场之旅 ——数位DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3598

数位DP...东看西看：http://www.cnblogs.com/Artanis/p/3751644.html

　　　　　　　　    https://www.cnblogs.com/MashiroSky/p/6399095.html

好巧妙的思路啊！这样统计的东西就变得很简单了；

好美的 dfs！数位DP用 dfs 好像能变得很清楚。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll l,r,f[65][6005],ans;
int n,a[65],K;
ll dfs1(int pos,int s,bool lim)
{if(pos==0)return s;if(!lim&&f[pos][s]!=-1)return f[pos][s];int end=K-1; ll ret=0;if(lim)end=a[pos];for(int i=0;i<=end;i++)ret+=dfs1(pos-1,s+i*(pos-1),lim&&(i==end));if(!lim)f[pos][s]=ret;//!lim!return ret;
}
ll dfs(int pos,int s,int m,bool lim)
{if(s<0)return 0;//!if(pos==0)return s;if(!lim&&f[pos][s]!=-1)return f[pos][s];int end=K-1; ll ret=0;if(lim)end=a[pos];for(int i=0;i<=end;i++){if(pos>=m)ret+=dfs(pos-1,s+i,m,lim&&(i==end));else ret+=dfs(pos-1,s-i,m,lim&&(i==end));}if(!lim)f[pos][s]=ret;return ret;
}
ll calc(ll x)
{int n=0;while(x)a[++n]=x%K,x/=K;memset(f,-1,sizeof f);ll ret=dfs1(n,0,1);for(int i=2;i<=n;i++){memset(f,-1,sizeof f);ret-=dfs(n,0,i,1);}    return ret;
}
int main()
{scanf("%lld%lld%d",&l,&r,&K);printf("%lld\n",calc(r)-calc(l-1));return 0;
}