题目描述

对数组最左边两个数进行(x+y)%10或(x*y)%10操作，直到数组只剩一个数，最后一个数为0-9之间的数，计算所有可能的操作后最后一个数字为0的操作数…为1的操作数…为2的操作数…

算法1

DP $f[i][j]$ 表示令第i个位置中j值出现的操作次数, 状态转移：$f[i - 1][j]$->$f[i][j + or * 当前位置的值]$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <initializer_list>

using namespace std;

typedef long long LL;
typedef long double LD;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int,int> PII;

const double PI = acos(-1.0);
const double eps = 1e-6;
//const LL mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+10;
const int maxm = 100+10;
//#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int mod = 998244353;

int f[maxn][10], a[maxn];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    f[0][0] = 1;//初始化最开始0值出现次数为1
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < 10; j ++ )
        {
            (f[i][(a[i] + j) % 10] += f[i - 1][j]) %= mod;
            if (i > 1) (f[i][(a[i] * j) % 10] += f[i - 1][j]) %= mod;
        }
    for (int i = 0; i < 10; i ++ ) cout << f[n][i] << endl;
}

int main() 
{  
    int T = 1;
    //scanf("%d", &T);  
    while (T -- ) solve();
    return 0;  
}