题解 | #小红删数字#

思路

（其实是一个 atcoder abc 的原题，但是牛客做了很多很多改动然后wa 了 114514 发……）

我们观察例如 ，那么我们 reverse 从前往后更好操作一点 ，然后记录到第 位操作的可能是多少，就可以得到一个转移方程，设第 次操作后当前数为 ，其（加法）转移方程为：

即第 位通过 与 加法得到的 的方法数就加上之前 步得到 的方法数，同理乘法是：

那么边界条件为:

然后填充 表即可，答案是进行到第 步后对 循环输出即可。时间复杂度为 ，空间复杂度 。

然而注意到最后答案只需要 的值，所以可以滚动掉 （但是我这里就不滚动了）。

AC Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll MOD = 1e9 + 7;
static array<array<ll, 10>, 200005> dp;
int main()
{
    ll n;
    cin >> n;
    vector<ll> vi(n);
    for (ll i = 0; i < n; i++)
        cin >> vi[i];

    reverse(vi.begin(), vi.end());

    if (n == 1)
    {
        for (int i = 0; i < 10; i++)
        {
            if (vi[0] == i)
            {
                cout << 1 << " ";
            }
            else
                cout << "0 ";
        }
        return 0;
    }

    dp[0][vi[0] % 10] = 1;
    for (ll i = 0; i < n - 1; i++)
    {
        for (ll j = 0; j < 10; j++)
        {
            ll cur = dp[i][j];
            if (!cur)
                continue;
            dp[i + 1][(j + vi[i + 1]) % 10] = (dp[i + 1][(j + vi[i + 1]) % 10] + cur) % MOD;
            dp[i + 1][(j * vi[i + 1]) % 10] = (dp[i + 1][(j * vi[i + 1]) % 10] + cur) % MOD;
        }
    }

    for (ll i = 0; i < 10; i++)
    {
        cout << dp[n - 1][i] << " ";
    }
}