算法
(动态规划) $O(10N)$
记 dp[i][j]
表示执行 $i$ 次操作且最后得到的数字为 $j$ 的方案数
转移方程:
$ \begin{aligned} & dp[i+1][(j + a_i) \% 10] = dp[i+1][(j + a_i) \% 10] + dp[i][j] \\\ & dp[i+1][(j \cdot a_i) \% 10] = dp[i+1][(j \cdot a_i) \% 10] + dp[i][j] \end{aligned} $
为节省空间可以压掉第一维
初始状态:
$dp[a[0]] = 1$,其余状态为 $0$
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using mint = modint998244353;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<mint> dp(10);
dp[a[0]] = 1;
for (int i = 1; i < n; ++i) {
int na = a[i];
vector<mint> p(10);
swap(dp, p);
rep(j, 10) {
dp[(j + na) % 10] += p[j];
dp[(j * na) % 10] += p[j];
}
}
rep(i, 10) cout << dp[i].val() << '\n';
return 0;
}