PKU 1790 Base Numbers

http://poj.org/problem?id=1790
与えられた数字列を数字と基数の組み合わせと見た時、何通りの表記として解釈できるかを答えろというような問題。

0の扱いに注意してやる必要がある以外はだいたいDP。
2回WAをもらいました。
サンプルだけだと不親切なので、問題分の数字列についても試すべきでした。

string in;
string base;

ll memo[100];
bool vis[100];

bool ok(int s,int e){
  if((e-s>1 && in[s]=='0') ||
     SZ(base)<e-s)return false;
  if(s==0 && e==1 &&
     in[0]=='0' && e+SZ(base)!=SZ(in))return false;
  if(SZ(base)>e-s)return true;
  for(int i=0;i<SZ(base);++i){
    if(base[i]<in[s+i])return false;
    if(base[i]>in[s+i])return true;
  }
  return false;
}

ll rec(int p){
  if(p==0)return 1;
  if(vis[p])return memo[p];
  vis[p]=true;
  ll& ret=memo[p]=0;
  rep(i,p)
    if(ok(i,p))ret+=rec(i);
  return ret;
}

void solve(){
  ll ans=0;
  for(int i=1;i<SZ(in);++i){
    if(in[i]=='0')continue;
    memset(vis,0,sizeof(vis));
    base=in.substr(i);
    ans+=rec(i);
  }
  
  cout<<"The code "<<in<<' ';
  if(ans)cout<<"can represent "<<ans<<" numbers."<<endl;
  else cout<<"is invalid."<<endl;
}

main(){
  while(cin>>in,in!="#")
    solve();
}