题目内容

小红有一个特异数组，初始这些数组都是正整数。如果这个数组长度大于 $1$ ，就需要将最后两个数取出进行运算，并将运算结果再加到数组末尾。

运算有加法和乘法两种。不同于正常的运算，运算得到的结果只会有一位，就是正常运算结果的最低位（个位）。

思路：动态规划

按照题意来进行DP。

定义 $dp[i][j]$ 表示从第 $i$ 个数到第 $n$ 个数，进行加法和乘法的运算后，运算结果为 $j$ 的方案数。

假设第 $i$ 个数为 y，那么可以枚举第 $i+1$ 状态下结果为 $0$ 到 $9$ 的方案数。 用 $x$ 来表示。

那么状态转移就是 $dp[i + 1][x] => dp[i][(x \times y)\mod 10]$