fork(1) download 
  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. #define MAX_N 110
  5. #define MAX_D 120000
  6. string S; int D; int num[MAX_N][10]; int dp[MAX_N][MAX_D];
  7. int main() {
  8. 	cin >> S >> D;
  9. 	for (int i = 0; i < S.size(); i++) {
  10. 		for (int j = 1; j < 10; j++) {
  11. 			if (i + j <= S.size()) {
  12. 				string T = S.substr(i, j);
  13. 				int M = stoi(T);
  14. 				num[i][j] = M;
  15. 			}
  16. 			else {
  17. 				num[i][j] = (1 << 30);
  18. 			}
  19. 		}
  20. 	}
  21. 	dp[0][0] = 1;
  22. 	for (int i = 1; i <= S.size(); i++) {
  23. 		for (int j = 0; j <= D; j++) {
  24. 			for (int k = 1; k < 10; k++) {
  25. 				if(i - k < 0){continue;}
  26. 				int target = j - num[i - k][k];
  27. 				if (target < 0) { continue; }
  28. 				dp[i][j] += dp[i - k][target];
  29. 				dp[i][j] %= 1000000007;
  30. 			}
  31. 		}
  32. 	}
  33. 	int sum = 0;
  34. 	for (int j = 0; j <= D; j++) {
  35. 		sum += dp[S.size()][j]; sum %= 1000000007;
  36. 	}
  37. 	cout << sum << endl;
  38. 	return 0;
  39. }
  40.  
Success #stdin #stdout 0s 55032KB
comments (?)
stdin 
1355
50
stdout 
3
https://ideone.com/bOvpLJ
language:
C++14 (gcc 8.3)
created:
8 years 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!