aoj2326:Number Sorting

問題文

Number Sorting | Aizu Online Judge

解法

dpしたい。Trie木使っていい感じにやるとできる。

使用メモリ量がやばくて、各データセットの終わりにTrie木のメモリを開放してやらないと終わる。

というかTrie木なんて使わなくても解けますね。悲しい。
aojで他人のコードを漁ったんですが、Trie木を書いてるコードが自分のものしかなくて死にたくなった。

コード

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
struct node{
    int val,sum;
    node *to[10];
 
    node(){
        val=sum=0;
        rep(i,10)to[i]=NULL;
    }
};
 
int A,B,P;
 
void insert(node *t,string &s,int i,int v){
    if(i==s.size()){
        t->val=v;
        t->sum=(t->sum+v)%P;
        return;
    }
 
    int c=s[i]-'0';
    if(t->to[c]==NULL){
        t->to[c]=new node();
    }
    t->sum=(t->sum-t->to[c]->sum+P)%P;
    insert(t->to[c],s,i+1,v);
    t->sum=(t->sum+t->to[c]->sum)%P;
}
 
int query(node *t,string &s,int i){
    int ret=0;
    int c=s[i]-'0';
    for(int j=0;j<c;j++)if(t->to[j]!=NULL)ret=(ret+t->to[j]->sum)%P;
    ret=(ret+t->val)%P;
    if(t->to[c]!=NULL)ret=(ret+query(t->to[c],s,i+1))%P;
    return ret;
}
 
void del(node *t){
    rep(i,10)if(t->to[i]!=NULL)del(t->to[i]);
    delete t;
}
 
signed main(){
    while(cin>>A>>B>>P,A||B||P){
        int ans=0;
        node *root=new node();
        for(int i=A;i<=B;i++){
            stringstream ss;
            ss<<i;
            string s=ss.str();
            int tmp=(query(root,s,0)+1)%P;
            ans=(ans+tmp)%P;
            insert(root,s,0,tmp);
        }
        cout<<ans<<endl;
 
        del(root);
    }
    return 0;
}