fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. ll Count(int N, ll C, int K, const string& S) {
  7.     string Cs = to_string(C);
  8.     int lenC = (int)Cs.size();
  9.     ll MOD = 1;
  10.     for (int i = 0; i < K; ++i) MOD *= 10;
  11.  
  12.     vector<ll> dp(N + 1, 0);
  13.     dp[N] = 1;
  14.  
  15.     for (int i = N - 1; i >= 0; --i) {
  16.         if (S[i] == '0') {
  17.             dp[i] = dp[i + 1]; // Only single '0' allowed
  18.             continue;
  19.         }
  20.         for (int j = i; j < N && j - i + 1 <= lenC; ++j) {
  21.             int length = j - i + 1;
  22.             string part = S.substr(i, length);
  23.  
  24.             // Compare substring 'part' with 'C' string for partition validity
  25.             if (length < lenC || (length == lenC && part <= Cs)) {
  26.                 dp[i] = (dp[i] + dp[j + 1]) % MOD;
  27.             } else {
  28.                 break; // no need to check longer substrings
  29.             }
  30.         }
  31.     }
  32.     return dp[0];
  33. }
  34.  
  35. int main() {
  36.     int N, K;
  37.     ll C;
  38.     string S;
  39.     cin >> N >> C >> K;
  40.     cin >> S;
  41.     cout << Count(N, C, K, S) << endl;
  42.     return 0;
  43. }
  44.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
7 1234567 9
1234567
stdout 
64
https://ideone.com/xzkx6f
language:
C++14 (gcc 8.3)
created:
3 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!