Here is a recursive algorithm of complexity $O(n^2 m)$ where there are $n$ symbols and the largest set of values replacing a symbol is $\lbrace 0, 1, ..., m-1 \rbrace$.

Let $m_i$ be the number of values replacing the $i$th symbol, $0\le i \lt n$. Without loss of generality, assume the $m_i$ are nondecreasing.

Define $f(a,b)$ be the number of distinct ways of ordering and replacing the last $a$ symbols so that each value is at least $b$. We want to compute $f(n,0)$.

If $m_0 = 0$ then $f(n,0)=0$ since there are no possible replacements. Otherwise, if we choose the number of $0$s to be z, then there are $n \choose z$ ways to place the $0$s, and there are $f(n-z,1)$ ways to choose the other symbols. So, $f(n,0) = \sum_z {n \choose z} f(n-z,1)$. More generally, if $m_{n-a} \le b$ then $f(a,b)=0$, otherwise

$$f(a,b) = \sum_{z=0}^a {a\choose z} f(a-z,b+1).$$

At the base of the recursion, $f(0,b)=1$.

Here is some Mathematica code which implements this with some examples

Clear[rec];
rec[a_, b_, mVec_] := rec[a, b, mVec] = 
   If[a == 0, 1, 
      If[mVec[[Length[mVec] - a + 1]] <= b, 0, 
         Sum[Binomial[a, z] rec[a - z, b + 1, mVec], {z, 0, a}]
        ]
     ]
rec[3, 0, {3, 3, 3}]
   27
rec[3, 0, {1, 2, 3}]
   16
rec[4, 0, {1, 2, 3, 4}]
   125
Timing[rec[20, 0, {12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50}]]
{0.031, 4822195074448408017997909570093056}

That last value is $2^{40}\times 3 \times 13^{19} = 12\times(52)^{19}$. There is a nice factorization when the $m_i$ are in an arithmetic progression which follows from the recursion. What is the origin of this problem?

Here is a recursive algorithm of complexity $O(n^2 m)$ where there are $n$ symbols and the largest set of values replacing a symbol is $\lbrace 0, 1, ..., m-1 \rbrace$.

Let $m_i$ be the number of values replacing the $i$th symbol, $0\le i \lt n$. Without loss of generality, assume the $m_i$ are nondecreasing.

Define $f(a,b)$ be the number of distinct ways of ordering and replacing the last $a$ symbols so that each value is at least $b$. We want to compute $f(n,0)$.

If $m_0 = 0$ then $f(n,0)=0$ since there are no possible replacements. Otherwise, if we choose the number of $0$s to be z, then there are $n \choose z$ ways to place the $0$s, and there are $f(n-z,1)$ ways to choose the other symbols. So, $f(n,0) = \sum_z {n \choose z} f(n-z,1)$. More generally, if $m_{n-a} \le b$ then $f(a,b)=0$, otherwise

$$f(a,b) = \sum_{z=0}^a {a\choose z} f(a-z,b+1).$$

At the base of the recursion, $f(0,b)=1$.

Here is some Mathematica code which implements this with some examples.

Clear[rec];
rec[a_, b_, mVec_] := rec[a, b, mVec] = 
   If[a == 0, 1, 
      If[mVec[[Length[mVec] - a + 1]] <= b, 0, 
         Sum[Binomial[a, z] rec[a - z, b + 1, mVec], {z, 0, a}]
        ]
     ]
rec[3, 0, {3, 3, 3}]
   27
rec[3, 0, {1, 2, 3}]
   16
rec[4, 0, {1, 2, 3, 4}]
   125
Timing[rec[20, 0, {12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50}]]
{0.031, 4822195074448408017997909570093056}

That last value is $2^{40}\times 3 \times 13^{19} = 12\times(52)^{19}$. There is a nice factorization when the $m_i$ are in an arithmetic progression which follows from the recursion.

Edit: The pattern above is in Stanley, Enumerative Combinatorics Volume 2, see Ex. 5.49.

Yuan, "On the Enumeration of Generalized Parking Functions" considered the OP's problem and proved some more general formulas where the maximums $m_i$ are a join of two linear functions, either $\lbrace a, a+b, a+2b, ... a+kb, m, m, m, ...m\rbrace$ or $\lbrace a, a+b, a+2b , ... a+kb, a+kb+c, a+kb+2c , ... \rbrace$ in my notation. These counts are single sums. It looks like the same techniques would express joins of more linear functions at the expense of iterated summation.