AtCoder Beginner Contest 220 D题

发布于 2022-02-20  731 次阅读


内容纲要

原题链接: https://atcoder.jp/contests/abc220/tasks/abc220_d

心态爆炸是这样的
单独拎出来写一下,因为当时整得我心态爆炸
其实现在回头看也不是很难hhhhhh....= =

题目大意:
给出一串数字,每次有两种可选操作:

1.取出最左边两个数,相加 % 10 然后把结果插回最左边。
2.取出最左边两个数,相乘 % 10 然后把结果插回最左边。

问在所有情况下最后剩下的那个数的个数,输出0-9的统计,数据范围1e5

题解:
1e5很明显不能搜的了,pow(2, 1e5)的复杂度和明显是不可接受的。
然后就是dp的特征咯,很明显无后效性,每一步之间是独立的,按步dp就行了。
还是要感谢寒假DP那组题,DP这块提升很大hhhhh

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

const int N = 1e5 + 10;
const int mod = 998244353;
int a[N];
long long f[15][N];

int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    f[a[1]][1] = 1;
    for(int i = 1; i < n; i++){
        for(int j = 0; j < 10; j++){
            f[(j * a[i + 1]) % 10][i + 1] += f[j][i];
            f[(j + a[i + 1]) % 10][i + 1] += f[j][i];
            f[(j * a[i + 1]) % 10][i + 1] %= mod;
            f[(j + a[i + 1]) % 10][i + 1] %= mod;
        }
    }

    for(int i = 0; i < 10; i++){
        printf("%d\n", f[i][n]);
    }
}

不爱嘉然小姐十年了。十年里,爱过的每个人都像她。