Codeforces 465E - Substitutes in Number

Problem Statement:
465E - Substitutes in Number

Solution:
A nice DP problem. Let val[i] be the "real" value of digit i. At first, val[i] = i, since every digit is not yet replaced by any strings. We compute val[i] after every replacement operations have been carried out, then in the end we can just iterate through the original string of digits \(s\) and replace each digit i in \(s\) by val[i].

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
long long MOD = (long long) 1e9 + 7LL;
int N;
int d[100005];
string t[100005];
long long val[11];
long long q[11];

int main(){
    cin >> t[0];
    d[0] = 0;
    scanf("%d", &N);
    for(int i=1;i<=N;++i){
        scanf("%d", &d[i]);
        cin >> t[i];
        t[i].erase(0, 2);
    }
    for(int i=0;i<10;++i){
        val[i] = i;
        q[i] = 10;
    }
    for(int i=N;i>=0;--i){
        int tlen = t[i].size();
        long long tval = 0;
        long long p10 = 1;
        for(int j=tlen-1;j>=0;--j){
            int g = t[i][j] - '0';
            tval += p10 * val[g];
            tval %= MOD;
            p10 *= q[g];
            p10 %= MOD;
        }
        val[d[i]] = tval;
        q[d[i]] = p10;
    }
    cout << val[0] << endl;
    return 0;
}