bzoj3598 [Scoi2014]方伯伯的商场之旅

时间:2022-01-20 10:32:41

数位dp,我们肯定枚举集合的位置,但是如果每次都重新dp的话会很麻烦,所以我们可以先钦定在最低位集合,dp出代价,然后再一步步找到正确的集合点,每次更改的代价也dp算就好了。

bzoj3598 [Scoi2014]方伯伯的商场之旅bzoj3598 [Scoi2014]方伯伯的商场之旅
 1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <cmath>
6 #define int long long
7 using namespace std;
8 int L,R,K;
9 int a[66];
10 int f[66][1500];
11 int dfs(int pos,int sum,int lim){
12 if(!pos)return sum;
13 if(!lim&&f[pos][sum]!=-1)return f[pos][sum];
14 int up=lim?a[pos]:K-1;
15 int ans=0;
16 for(int i=0;i<=up;i++)
17 ans+=dfs(pos-1,sum+(pos-1)*i,lim&&(i==up));
18 if(!lim)f[pos][sum]=ans;
19 return ans;
20 }
21 int dfs(int pos,int zd,int sum,int lim){
22 if(sum<0)return 0;
23 if(!pos)return sum;
24 if(!lim&&f[pos][sum]!=-1)return f[pos][sum];
25 int up=lim?a[pos]:K-1;
26 int ans=0;
27 for(int i=0;i<=up;i++){
28 if(pos>=zd)ans+=dfs(pos-1,zd,sum+i,lim&&(i==up));
29 else ans+=dfs(pos-1,zd,sum-i,lim&&(i==up));
30 }
31 if(!lim)f[pos][sum]=ans;
32 return ans;
33 }
34 int work(int x){
35 int pos=0;
36 while(x){
37 a[++pos]=x%K;
38 x/=K;
39 }
40 memset(f,-1,sizeof f);
41 int ans=dfs(pos,0,1);
42 for(int i=2;i<=pos;i++){
43 memset(f,-1,sizeof f);
44 ans-=dfs(pos,i,0,1);
45 }
46 return ans;
47 }
48 signed main(){
49 scanf("%lld%lld%lld",&L,&R,&K);
50 printf("%lld\n",work(R)-work(L-1));
51 return 0;
52 }
View Code