fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8.  
  9.  
  10. //_ ***************************** START Below *******************************
  11.  
  12.  
  13.  
  14.  
  15. const int MOD = 1000000007;
  16. const int N = 3e5+9;
  17. const int INF = 2e9+1;
  18. const int LINF = 2000000000000000001;
  19. const int MAX_VAL = 5000;
  20.  
  21. int countArrays(vector<int> a) {
  22.     int n = a.size();
  23.     if (n == 0) return 0;
  24.  
  25.     auto getDigitSum = [](int x) {
  26.         int sum = 0;
  27.         x = abs(x); // Safe guard just in case
  28.         while (x > 0) {
  29.             sum += x % 10;
  30.             x /= 10;
  31.         }
  32.         return sum;
  33.     };
  34.  
  35.     vector<int> digitSum(MAX_VAL + 1);
  36.     for (int i = 1; i <= MAX_VAL; ++i) {
  37.         digitSum[i] = getDigitSum(i);
  38.     }
  39.  
  40.     vector<int> dp(MAX_VAL + 1, 0);
  41.  
  42.     for (int i = 1; i <= MAX_VAL; ++i) {
  43.         if (digitSum[i] == a[0]) {
  44.             dp[i] = 1;
  45.         }
  46.     }
  47.  
  48.     for (int i = 1; i < n; ++i) {
  49.         vector<int> pref(MAX_VAL + 1, 0);
  50.  
  51.         pref[1] = dp[1];
  52.         for (int j = 2; j <= MAX_VAL; ++j) {
  53.             pref[j] = (pref[j - 1] + dp[j]) % MOD;
  54.         }
  55.  
  56.         for (int j = 1; j <= MAX_VAL; ++j) {
  57.             if (digitSum[j] == a[i]) {
  58.                 dp[j] = pref[j];
  59.             } else {
  60.                 dp[j] = 0;
  61.             }
  62.         }
  63.     }
  64.  
  65.     int ways = 0;
  66.     for (int i = 1; i <= MAX_VAL; ++i) {
  67.         ways = (ways + dp[i]) % MOD;
  68.     }
  69.  
  70.     return ways;
  71. }
  72.  
  73. // int countArrays(vector<int> a) {
  74. //     int n = a.size();
  75. //     if (n == 0) return 0;
  76.  
  77. //     auto getDigitSum = [](int x) {
  78. //         int sum = 0;
  79. //         while (x > 0) {
  80. //             sum += x % 10;
  81. //             x /= 10;
  82. //         }
  83. //         return sum;
  84. //     };
  85.  
  86. //     vector<int> digitSum(MAX_VAL + 1);
  87. //     for (int i = 0; i <= MAX_VAL; ++i) {
  88. //         digitSum[i] = getDigitSum(i);
  89. //     }
  90.  
  91. //     vector<int> dp(MAX_VAL + 1, 0);
  92.  
  93. //     for (int i = 0; i <= MAX_VAL; ++i) {
  94. //         if (digitSum[i] == a[0]) {
  95. //             dp[i] = 1;
  96. //         }
  97. //     }
  98.  
  99. //     for (int i = 1; i < n; ++i) {
  100. //         vector<int> pref(MAX_VAL + 1, 0);
  101. //         pref[0] = dp[0];
  102.  
  103. //         for (int j = 1; j <= MAX_VAL; ++j) {
  104. //             pref[j] = (pref[j - 1] + dp[j]) % MOD;
  105. //         }
  106.  
  107. //         for (int j = 0; j <= MAX_VAL; ++j) {
  108. //             if (digitSum[j] == a[i]) {
  109. //                 dp[j] = pref[j];
  110. //             } else {
  111. //                 dp[j] = 0;
  112. //             }
  113. //         }
  114. //     }
  115.  
  116. //     int ways = 0;
  117. //     for (int i = 0; i <= MAX_VAL; ++i) {
  118. //         ways = (ways + dp[i]) % MOD;
  119. //     }
  120.  
  121. //     return ways;
  122. // }
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131. void solve() {
  132.  
  133. 	int n;
  134. 	cin >> n;
  135.  
  136. 	vector<int> a(n);
  137. 	for(int i=0; i<n; i++) cin >> a[i];
  138.  
  139. 	cout << countArrays(a) << endl;
  140.  
  141.  
  142. }
  143.  
  144.  
  145.  
  146.  
  147.  
  148. int32_t main() {
  149.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  150.  
  151.     int t = 1;
  152.     cin >> t;
  153.     while (t--) {
  154.         solve();
  155.     }
  156.  
  157.     return 0;
  158. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
2
1 31
5
31 7 23 17 1
stdout
copy 
4
0
https://ideone.com/ItE175
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

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!