原题链接: 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]);
}
}