fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std; 
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii; 
  7.  
  8. const int N = 1e5 + 5; 
  9. const int MOD = 998244353;  
  10.  
  11. void add(int& a, int b) {
  12. 	a += b; 
  13. 	if (a >= MOD) a -= MOD; 
  14. }
  15.  
  16. int n;  
  17. int a[N];  
  18.  
  19. int dp[N][10]; // dp[i][val] = Số cách để tạo ra giá trị val (0 <= val <= 9) từ i phần tử đầu tiên
  20.  
  21. int main() {
  22. 	ios::sync_with_stdio(false); 
  23. 	cin.tie(nullptr);  
  24. 	cin >> n;  
  25. 	for (int i = 1; i <= n; i++) cin >> a[i];   
  26.  
  27. 	// Khởi tạo cho 2 phần tử đầu tiên 
  28. 	dp[2][(a[1] + a[2]) % 10] = 1; 
  29. 	add(dp[2][(a[1] * a[2]) % 10], 1); 
  30.  
  31. 	for (int i = 3; i <= n; i++) {
  32. 		// Gọi prev_val là giá trị khi gộp i - 1 phần tử trước đó
  33. 		// Từ prev_val, a[i] và loại thao tác áp dụng hiện tại là F hay G, ta tính ra được giá trị gộp mới
  34. 		for (int prev_val = 0; prev_val <= 9; prev_val++) {	
  35. 			add(dp[i][(prev_val + a[i]) % 10], dp[i - 1][prev_val]); 
  36. 			add(dp[i][(prev_val * a[i]) % 10], dp[i - 1][prev_val]); 				
  37. 		}
  38. 	}
  39.  
  40. 	for (int val = 0; val <= 9; val++) {
  41. 		cout << dp[n][val] << '\n'; 
  42. 	}
  43. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
3
2 7 6
stdout 
1
0
0
0
2
1
0
0
0
0
https://ideone.com/3gFd5n
language:
C++14 (gcc 8.3)
created:
57 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!