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