好时光 题解

``` #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxk=61; const int maxn=19; const int maxl=110; typedef long long ll; const int mod=19260821; ll k,l,n[maxl],r; int f[maxn][maxn][maxn][maxk][maxk]; char s[maxl]; inline void upd(int&x,int v){x+=v;while(x>=mod)x-=mod;} vector<int>dim; int dfs(register int x,register int lgt,register int nww,register int lls,register int ls,register bool op) { if(!x)return max(lgt,nww); if(!op&&~f[x][lgt][nww][lls][ls])return f[x][lgt][nww][lls][ls]; int maxx=op?dim[x]:(k-1),ret=0; for(int i=0;i<=maxx;i++) { if(lls==k&&ls==k) { if(i)upd(ret,dfs(x-1,1,1,k,i,op&(i==maxx))); else upd(ret,dfs(x-1,0,0,k,k,op&(i==maxx))); } else if(lls==k)upd(ret,dfs(x-1,2,2,ls,i,op&(i==maxx))); else if(ls-lls==i-ls)upd(ret,dfs(x-1,max(lgt,nww+1),nww+1,ls,i,op&(i==maxx))); else upd(ret,dfs(x-1,lgt,2,ls,i,op&(i==maxx))); } return f[x][lgt][nww][lls][ls]=ret; } int main() { memset(f,-1,sizeof f); scanf("%s%lld",s,&k); l=strlen(s); for(int i=0;i<l;i++)n[i]=s[l-i-1]-'0'; dim.push_back(-1); while(l) { r=0; for(int i=l-1;i>=0;i--) { int t=r; r=(r*10+n[i])%k; n[i]=(t*10+n[i])/k; } while(l&&!n[l-1])l--; dim.push_back(r); } printf("%d\n",dfs(dim.size()-1,0,0,k,k,true)); return 0; } ```