思路：动态规划

按照题意来进行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]$

由于第 $i$ 个状态都是由第 $i+1$ 状态转移而来，所以可以用滚动数组优化。

时间复杂度：$O(10n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    stack<int> stk;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        stk.push(x);
    }


    vector<int> dp(10, 0);
    
    // 特判 n=1 的情况
    if (n == 1) {
        if (stk.top() < 10) dp[stk.top()] = 1;
        for (int i = 0; i < 10; ++i) cout << dp[i] << " \n"[i == 9];
        return 0;
    }

    // 初始化 dp[n][0~9] 的状态
    dp[stk.top() % 10] = 1;
    stk.pop();

    while (!stk.empty()) {
        int t = stk.top() % 10; stk.pop();
        // 滚动数组优化，ndp 此时表示 dp[i][0~9] 状态
        // dp数组 表示 dp[i+1][0~9] 状态
        vector<int> ndp(10, 0);

        // 枚举第 i+1 状态下结果为 0~9
        for (int i = 0; i < 10; ++i) {
            ndp[(i + t) % 10] += dp[i];
            ndp[(i + t) % 10] %= MOD;
            ndp[i * t % 10] += dp[i];
            ndp[i * t % 10] %= MOD;
        }
        
        // 最后更新 dp ，使得其由 dp[i+1] 状态转换为最新的 dp[i] 
        swap(dp, ndp);
    }

    for (int i = 0; i < 10; ++i) cout << dp[i] << " \n"[i == 9];
    return 0;
}

python

MOD = int(1e9) + 7

n = int(input())

stk = list(map(int, input().split()))

dp = [0] * 10

# Special case for n = 1
if n == 1:
    if stk[-1] < 10:
        dp[stk[-1]] = 1
    print(*dp)
    exit(0)

dp[stk[-1] % 10] = 1
stk.pop()

while stk:
    t = stk[-1] % 10
    stk.pop()
    ndp = [0] * 10

    for i in range(10):
        ndp[(i + t) % 10] += dp[i]
        ndp[(i + t) % 10] %= MOD
        ndp[i * t % 10] += dp[i]
        ndp[i * t % 10] %= MOD

    dp = ndp

print(*dp)

Java

import java.util.Scanner;

public class Main {
    static final int MOD = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] stk = new int[n];
        for (int i = 0; i < n; i++) {
            stk[i] = scanner.nextInt();
        }

        int[] dp = new int[10];

        // 特判 n=1 的情况
        if (n == 1) {
            if (stk[n - 1] < 10) {
                dp[stk[n - 1]] = 1;
            }
            for (int i = 0; i < 10; i++) {
                System.out.print(dp[i] + " ");
            }
            return;
        }

        dp[stk[n - 1] % 10] = 1;
        n--;

        while (n > 0) {
            int t = stk[n - 1] % 10;
            n--;
            // 滚动数组优化，ndp 此时表示 dp[i][0~9] 状态
            // dp数组 表示 dp[i+1][0~9] 状态
            int[] ndp = new int[10];

            for (int i = 0; i < 10; i++) {
                ndp[(i + t) % 10] += dp[i];
                ndp[(i + t) % 10] %= MOD;
                ndp[i * t % 10] += dp[i];
                ndp[i * t % 10] %= MOD;
            }

            // 最后更新 dp ，使得其由 dp[i+1] 状态转换为最新的 dp[i] 
            dp = ndp;
        }

        for (int i = 0; i < 10; i++) {
            System.out.print(dp[i] + " ");
        }
    }
}

题目内容

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

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

例如，对于数组$[1,3,1,4]$，选择加法运算后，数组变为$[1,3,5]$，再接着选择第二种操作后，数组变为$[1,5]$。

现在，小红想问你，当特异数组只剩下一个数时，这个数为 $0,1,2,...,9$ 的可能有多少，换句话说，让你输出这 $10$ 个数为最终剩余的一个数的方案数，答案对 $10^9+7$ 取模。

输入描述

第一行，正整数$n$，代表特异数组的初始长度。

第二行，n个正整数$a_1，a_2，......，a_n$，代表初始的特异数组。

$1 \leq n \leq 200000$

$1 \leq a_i \leq 10^9$

输出描述

一行，$10$个整数，第$i$个数代表结果为$i$的方案数

样例

输入输出示例仅提供调试，后台判断数据一般不包含示例

输入

4
1 3 1 4

输出

0 0 1 1 0 1 1 1 2 1