fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4.  
  5. using namespace std;
  6.  
  7.  
  8. const int N = 1e6 + 5;
  9. int b;
  10. string y;
  11. int dp[N]; //Menyimpan banyaknya kemungkinan [0, i]
  12. const int mod = 1e9 + 7;
  13. /*
  14. Lompatan rekursi kita itu bakal sampai n (length dari y)
  15. Kalau kita sudah mencapai tujuan kita artinya ini merupakan solusi valid
  16. */
  17.  
  18. /*
  19. ll knapsack(int cur, int weight) {
  20.     int skip = knapsack(cur + 1, weight);
  21.     int take = knapsack(cur + 1, weight - h[cur]) + val[cur];
  22. }
  23. */
  24.  
  25. int rec(int cur) {
  26.     if (cur >= y.length()) {
  27.         return 1;
  28.     }
  29.     if (dp[cur] != -1) return dp[cur];
  30.     int ans = rec(cur + 1);
  31.     int m = y.length() - cur;
  32.     for (int i = 2; i <= m && y[cur] != '0'; i++) {
  33.         string tmp = y.substr(cur, i);
  34.         ll cmp = stoll(tmp);
  35.         if (cmp < b) {
  36.             (ans += rec(cur + i)) %= mod;
  37.         } else {
  38.             break;
  39.         }
  40.     }
  41.     dp[cur] = ans;
  42.     return dp[cur];
  43. }
  44.  
  45. int main() {
  46.     cin.tie(0) -> sync_with_stdio(false), cout.tie(0);
  47.     cin >> b >> y;
  48.     bool ok = 1;
  49.     memset(dp, -1, sizeof dp);
  50.     for (auto c : y) {
  51.         if (c - '0' >= b) {
  52.             ok = 0;
  53.         }
  54.     }
  55.     if (ok) {
  56.         cout << rec(0) << '\n';
  57.     } else {
  58.         cout << "0\n";
  59.     }
  60.     return 0;
  61. }
Success #stdin #stdout 0.01s 7488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/sRFAca
language:
C++ (gcc 8.3)
created:
1 day 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!