问题理解

我们有一个长度为 ( N ) 的整数序列 ( A = (A_1, A_2, \ldots, A_N) )，其中每个整数 ( A_i ) 都在 0 到 9 之间。我们需要对这个序列进行一系列操作，直到序列的长度变为 1。每次操作可以选择以下两种之一：

1. 操作 F：删除最左边的两个数 ( x ) 和 ( y )，然后将 ( (x + y) % 10 ) 插入到序列的最左端。
2. 操作 G：删除最左边的两个数 ( x ) 和 ( y )，然后将 ( (x \times y) % 10 ) 插入到序列的最左端。

最终，我们需要计算在所有可能的操作序列中，最终序列中的唯一一个数等于 ( K )（( K = 0, 1, \ldots, 9 )）的情况有多少种。由于结果可能非常大，我们需要对结果取模 ( 998244353 )。

问题分析

这个问题可以通过动态规划（Dynamic Programming, DP）来解决。我们需要考虑每一步操作对序列的影响，并记录每一步可能的中间结果。

动态规划状态定义

我们可以定义 ( dp[i][j] ) 表示在处理到第 ( i ) 个数时，当前序列的最左端数字为 ( j ) 的方案数。由于每一步操作都涉及到两个数，我们需要考虑每一步操作对当前序列的影响。

转移方程

对于每一步操作，我们有两种选择：操作 F 或操作 G。假设当前序列的最左端数字为 ( x )，下一个数字为 ( y )，那么：

1. 操作 F：新的最左端数字为 ( (x + y) % 10 )。
2. 操作 G：新的最左端数字为 ( (x \times y) % 10 )。

因此，转移方程可以表示为：

[ dp[i][(x + y) % 10] += dp[i-1][x] ] [ dp[i][(x \times y) % 10] += dp[i-1][x] ]

初始条件

初始时，序列中只有一个数 ( A_1 )，因此 ( dp[1][A_1] = 1 )。

最终结果

最终，我们需要计算所有可能的操作序列中，最终序列中的唯一一个数等于 ( K ) 的方案数。这可以通过遍历所有可能的中间状态并累加相应的方案数来实现。

C++ 代码实现

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

const int MOD = 998244353;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Initialize DP table
    vector<unordered_map<int, int>> dp(N);
    dp[0][A[0]] = 1;

    for (int i = 1; i < N; ++i) {
        int current_num = A[i];
        unordered_map<int, int> new_dp;
        for (auto& [prev_num, count] : dp[i-1]) {
            // Operation F
            int new_num_F = (prev_num + current_num) % 10;
            new_dp[new_num_F] = (new_dp[new_num_F] + count) % MOD;
            // Operation G
            int new_num_G = (prev_num * current_num) % 10;
            new_dp[new_num_G] = (new_dp[new_num_G] + count) % MOD;
        }
        dp[i] = new_dp;
    }

    // The final result is the count of each K in the last DP state
    vector<int> final_counts(10, 0);
    for (auto& [num, count] : dp[N-1]) {
        final_counts[num] = count;
    }

    for (int k = 0; k < 10; ++k) {
        cout << final_counts[k] << endl;
    }

    return 0;
}

对于样例1

初始状态

• 初始序列为 ( (2, 7, 6) )。
• 定义 ( dp[i][j] ) 表示处理到第 ( i ) 个数时，当前序列的最左端数字为 ( j ) 的方案数。
• 初始状态：( dp[0][2] = 1 )。

第一步操作

• 操作 F：

  • 删除最左边的两个数 ( 2 ) 和 ( 7 )。
  • 计算 ( (2 + 7) % 10 = 9 )。
  • 将 ( 9 ) 插入到序列的最左端。
  • 更新 ( dp[1][9] = 1 )。

• 操作 G：

  • 删除最左边的两个数 ( 2 ) 和 ( 7 )。
  • 计算 ( (2 \times 7) % 10 = 4 )。
  • 将 ( 4 ) 插入到序列的最左端。
  • 更新 ( dp[1][4] = 1 )。

• 状态更新：

  • ( dp[1] = {9: 1, 4: 1} )。

第二步操作

• 对于 ( dp[1][9] = 1 )：

  • 操作 F：

    • 删除最左边的两个数 ( 9 ) 和 ( 6 )。
    • 计算 ( (9 + 6) % 10 = 5 )。
    • 将 ( 5 ) 插入到序列的最左端。
    • 更新 ( dp[2][5] = 1 )。

  • 操作 G：

    • 删除最左边的两个数 ( 9 ) 和 ( 6 )。
    • 计算 ( (9 \times 6) % 10 = 4 )。
    • 将 ( 4 ) 插入到序列的最左端。
    • 更新 ( dp[2][4] = 1 )。

• 对于 ( dp[1][4] = 1 )：

  • 操作 F：

    • 删除最左边的两个数 ( 4 ) 和 ( 6 )。
    • 计算 ( (4 + 6) % 10 = 0 )。
    • 将 ( 0 ) 插入到序列的最左端。
    • 更新 ( dp[2][0] = 1 )。

  • 操作 G：

    • 删除最左边的两个数 ( 4 ) 和 ( 6 )。
    • 计算 ( (4 \times 6) % 10 = 4 )。
    • 将 ( 4 ) 插入到序列的最左端。
    • 更新 ( dp[2][4] = 1 )。

• 状态更新：

  • ( dp[2] = {5: 1, 4: 2, 0: 1} )。

最终结果

• 最终序列的可能值为 ( 0, 4, 5 )。
• 统计每种可能的方案数：
  • ( K = 0: 1 )
  • ( K = 1: 0 )
  • ( K = 2: 0 )
  • ( K = 3: 0 )
  • ( K = 4: 2 )
  • ( K = 5: 1 )
  • ( K = 6: 0 )
  • ( K = 7: 0 )
  • ( K = 8: 0 )
  • ( K = 9: 0 )