题解 | #小红删数字#

动态规划

考虑 $dp[i][j]$ ，操作完第 $i$ 项后，结果为 $j$ 的方案数，每一轮操作的数字 $j$ 会变成 $(j + arr[i])\pmod{10}$ 和 $(j \times arr[i])\pmod{10}$ ，不难写出转移方程

\begin{aligned} dp[i][(j + arr[i])\pmod{10}] += dp[i+1][j] \\ dp[i][(j \times arr[i])\pmod{10}] += dp[i+1][j] \end{aligned}

我们在转移的时候开一个辅助数组tmp去滚，dp的第一维可以省略掉，时间复杂度 $O(n)$ ，注意 $n=1$ 的时候，大于等于 $10$ 的数字不能算在计数里，下面贴代码


/*

##     ##   #######   ########    ###     ########  ##   ##
##     ##  ##     ##     ##      ## ##    ##    ##  ##   ##
##     ##  ##     ##     ##     ##   ##   ##    ##  ##   ##
#########  ##     ##     ##    ##     ##  ########  ##   ##
##     ##  ##     ##     ##    #########  ##  ##    ##   ##
##     ##  ##     ##     ##    ##     ##  ##   ##   ##   ##
##     ##   #######      ##    ##     ##  ##    ##   #####

*/
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define int long long
#define endl '\n'
#define rep(i,a,b) for(int i = a ; i <= b ; i++)
#define per(i,a,b) for(int i = a ; i >= b ; i--)
using namespace std;
const int MOD = 1e9+7;
void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> dp(10);
    rep(i,0,n-1)cin >> arr[i];
    if (n > 1)dp[arr[n-1] % 10]++;
    else if (arr[n-1] < 10)dp[arr[n-1]]++;
    per(i,n-2,0) {
        vector<int> tmp(10);
        rep(j,0,9) {
            tmp[(j + arr[i])%10] += dp[j],tmp[(j + arr[i])%10] %= MOD;
            tmp[(j * arr[i])%10] += dp[j],tmp[(j * arr[i])%10] %= MOD;
        }
        dp.swap(tmp);
    }
    rep(i,0,9) {
        cout << dp[i] << " ";
    }
    cout << endl;
}
signed main() {
    IOS;
    solve();
    return 0;
}