fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int B;
  5. string Y;
  6. int memo[100001];
  7. const int MOD = 1e9+7;
  8.  
  9. int DP(int index) {
  10. 	if(index >= Y.size()) return 1;
  11. 	if(memo[index] != -1) return memo[index];
  12. 	if(Y[index] == '0') return memo[index] = DP(index+1);
  13. 	int digit = 0, ans = 0, next = index;
  14. 	while(next < Y.size() && digit < B) {
  15. 		digit = 10*digit + (Y[next++]-'0');
  16. 		if(digit >= B) break;
  17. 		// cout << index << " " << digit << endl;
  18. 		ans = (ans+DP(next))%MOD;
  19. 	}
  20. 	return memo[index] = ans;
  21. }
  22.  
  23. int main() {
  24. 	cin >> B >> Y;
  25. 	for(int i = 0; i < Y.size(); i++)
  26. 		memo[i] = -1;
  27. 	/*
  28. 	for(int i = 0; i < Y.size(); i++)
  29. 		cout << DP(i) << " ";
  30. 	cout << endl;
  31. 	/**/
  32. 	cout << DP(0) << endl;
  33. 	return 0;
  34. }
  35. /*
  36. 01234567
  37. 71112016
  38.  
  39. DP(X) = berapa banyak kemungkinan input untuk
  40.         string mulai index ke-X
  41.         
  42. DP(0) = seluruh string
  43. DP(4) = untuk string "2016"
  44. DP(7) = untuk string "6"
  45. DP(8) = 1
  46.  
  47. 71(1)12016
  48. 71(11)2016
  49.  
  50. DP(2) = DP("112016")
  51. = DP(3)
  52. + DP(4)
  53.  
  54. */
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
1000000
123456789123456789123456789123456789
stdout
copy 
649774399
https://ideone.com/dAYW3i
language:
C++ (gcc 8.3)
created:
25 days 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!