fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. typedef long long ll;  
  5.  
  6. const int N = 1e5 + 5; 
  7. const int MOD = 998244353;  
  8.  
  9. int n;  
  10. int a[N];  
  11.  
  12. 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
  13.  
  14. int main() {
  15. 	ios::sync_with_stdio(0); 
  16. 	cin.tie(0);  
  17. 	cin >> n;  
  18. 	for (int i = 1; i <= n; i++) cin >> a[i];   
  19.  
  20. 	dp[2][(a[1] + a[2]) % 10]++; 
  21. 	dp[2][(a[1] * a[2]) % 10]++; 
  22.  
  23. 	// nếu cài đặt kiểu get về: dp(i) truy hồi về dp(i - 1)
  24. 	// (a[i] + x) % 10 = val   
  25. 	// (a[i] * x) % 10 = val   
  26.  
  27. 	// nếu cài đặt kiểu update lên: dp(i) cập nhật lên cho dp(i + 1)
  28. 	// (val + a[i + 1]) % 10 = new_val   
  29. 	// (val * a[i + 1]) % 10 = new_val
  30.  
  31. 	for (int i = 2; i < n; i++) {
  32. 		for (int val = 0; val <= 9; val++) {
  33. 			(dp[i + 1][(val + a[i + 1]) % 10] += dp[i][val]) %= MOD; 
  34. 			(dp[i + 1][(val * a[i + 1]) % 10] += dp[i][val]) %= MOD; 				
  35. 		}
  36. 	}
  37.  
  38. 	for (int K = 0; K <= 9; K++) {
  39. 		cout << dp[n][K] << '\n'; 
  40. 	}
  41. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
2 7 6
stdout
copy 
1
0
0
0
2
1
0
0
0
0
https://ideone.com/6JdnH1
language:
C++14 (gcc 8.3)
created:
297 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!