fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // =====================================================================
  5. //                      DIGIT DP – MASTER TEMPLATE
  6. //                 (ECPC / ACPC / Advanced Tricks)
  7. // =====================================================================
  8.  
  9. /*
  10.    GENERAL INTRODUCTION TO DIGIT DP
  11.  
  12.    Digit DP is a technique that counts integers in a range (e.g., [0..N])
  13.    that satisfy a certain condition. It works by processing the decimal
  14.    digits from left to right (most significant to least).
  15.  
  16.    Common states used in recursion:
  17.      - pos     : current digit position (0 = most significant).
  18.      - tight   : are we still following the digits of N exactly?
  19.                  If tight == true, the next digit cannot exceed N[pos].
  20.                  If tight == false, we can choose any digit 0..9.
  21.      - started : have we placed a non‑zero digit yet? Used to ignore
  22.                  leading zeros so that numbers like "007" are treated as "7".
  23.  
  24.    Additional states depend on the specific problem (e.g., sum of digits,
  25.    product, modulo, bitmask of used digits, etc.).
  26.  
  27.    The template below collects many common variants.
  28.    Each function is documented as a black box – you only need to know
  29.    what it does and how to call it.
  30. */
  31.  
  32. // -------------------------------------------------------------
  33. // 1) BASIC DIGIT DP – count numbers <= N with a property
  34. //    (property: no two consecutive equal digits)
  35. // -------------------------------------------------------------
  36.  
  37. class DigitDP_Basic {
  38. public:
  39.     /*
  40.         FUNCTION: countNoConsecutiveEqual(const string& N)
  41.  
  42.         PURPOSE:
  43.           Counts all integers in the range [0, N] (inclusive) that do NOT have
  44.           two adjacent equal digits. For example, 121 is allowed, but 122 is not.
  45.  
  46.         PARAMETERS:
  47.           N (string) – the upper bound, given as a decimal string (e.g., "1000").
  48.  
  49.         RETURN:
  50.           long long – the number of valid integers.
  51.  
  52.         TIME COMPLEXITY:
  53.           O(len * 2 * 11) = O(len), where len = N.length().
  54.           (States: position, tight flag, and previous digit (0..9 or 10 for none).)
  55.  
  56.         CONSTRAINTS:
  57.           - N can be as long as memory allows (string length up to ~19 for 64‑bit,
  58.             but the code uses long long and recursion, so practical limit ~20 digits).
  59.           - The function handles leading zeros correctly (numbers with fewer digits).
  60.  
  61.         NOTES:
  62.           - The function treats 0 as a valid number (it has no consecutive digits).
  63.           - The recursion uses memoization to avoid repeated work.
  64.           - The 'last' parameter is 10 when no digit has been placed yet (sentinel).
  65.     */
  66.     long long countNoConsecutiveEqual(const string& N) {
  67.         int len = N.size();
  68.         // memo[pos][tight][last] where last in 0..10 (10 = no previous digit)
  69.         vector<vector<vector<long long>>> memo(len,
  70.                     vector<vector<long long>>(2, vector<long long>(11, -1)));
  71.  
  72.         function<long long(int,bool,int)> dfs = [&](int pos, bool tight, int last) -> long long {
  73.             if (pos == len) return 1; // one valid number (the empty prefix counts as 1)
  74.             if (!tight && memo[pos][tight][last] != -1)
  75.                 return memo[pos][tight][last];
  76.  
  77.             int limit = tight ? N[pos] - '0' : 9;
  78.             long long ans = 0;
  79.             for (int d = 0; d <= limit; d++) {
  80.                 if (last != 10 && d == last) continue; // no consecutive equal digits
  81.                 ans += dfs(pos + 1, tight && (d == limit), d);
  82.             }
  83.             if (!tight) memo[pos][tight][last] = ans;
  84.             return ans;
  85.         };
  86.         return dfs(0, true, 10); // start with no previous digit
  87.     }
  88. };
  89.  
  90. // -------------------------------------------------------------
  91. // 2) DIGIT DP WITH MULTIPLE CONSTRAINTS (sum, product, modulo)
  92. // -------------------------------------------------------------
  93.  
  94. /*
  95.     FUNCTION: countDigitSumMod(const string& N, int K)
  96.  
  97.     PURPOSE:
  98.       Counts numbers in [0, N] (inclusive) whose sum of digits is divisible by K.
  99.       Example: for N=20, K=3, numbers with digit sum % 3 == 0 are 0,3,6,9,12,15,18.
  100.  
  101.     PARAMETERS:
  102.       N (string) – upper bound as a string.
  103.       K (int)    – the divisor (must be > 0).
  104.  
  105.     RETURN:
  106.       long long – count of valid numbers.
  107.  
  108.     TIME COMPLEXITY:
  109.       O(len * 2 * 2 * K) = O(len * K), where len = N.length().
  110.       (States: pos, tight, started, modulo remainder.)
  111.  
  112.     CONSTRAINTS:
  113.       - K should be small enough to allocate a 4D vector of size len*2*2*K.
  114.         Typically K <= 1000 is fine.
  115.       - N length up to ~20 (since using recursion and 64‑bit return).
  116.  
  117.     NOTES:
  118.       - Leading zeros are ignored (the number 0 is counted if its digit sum 0 % K == 0).
  119.       - The function uses memoization.
  120. */
  121. long long countDigitSumMod(const string& N, int K) {
  122.     int len = N.size();
  123.     // dp[pos][tight][started][sum_mod]
  124.     vector<vector<vector<vector<long long>>>> memo(len,
  125.                 vector<vector<vector<long long>>>(2,
  126.                 vector<vector<long long>>(2, vector<long long>(K, -1))));
  127.  
  128.     function<long long(int,bool,bool,int)> dfs = [&](int pos, bool tight, bool started, int mod) -> long long {
  129.         if (pos == len) return (started && mod == 0) ? 1 : 0; // empty number not counted
  130.         if (!tight && memo[pos][tight][started][mod] != -1)
  131.             return memo[pos][tight][started][mod];
  132.  
  133.         int limit = tight ? N[pos] - '0' : 9;
  134.         long long ans = 0;
  135.         for (int d = 0; d <= limit; d++) {
  136.             int newMod = (mod + d) % K;
  137.             bool newStarted = started || (d != 0);
  138.             ans += dfs(pos + 1, tight && (d == limit), newStarted, newStarted ? newMod : 0);
  139.         }
  140.         if (!tight) memo[pos][tight][started][mod] = ans;
  141.         return ans;
  142.     };
  143.     return dfs(0, true, false, 0);
  144. }
  145.  
  146. /*
  147.     FUNCTION: countProductDivisible(const string& N, int M)
  148.  
  149.     PURPOSE:
  150.       Counts numbers in [0, N] (inclusive) such that the product of their digits
  151.       is divisible by M.
  152.       Example: N=100, M=5 -> numbers containing digit 0 or 5 have product divisible by 5.
  153.  
  154.     PARAMETERS:
  155.       N (string) – upper bound.
  156.       M (int)    – the divisor (M > 0).
  157.  
  158.     RETURN:
  159.       long long – count of valid numbers.
  160.  
  161.     TIME COMPLEXITY:
  162.       O(len * 2 * 2 * M) if M is small. For larger M, we can use map to store sparse states,
  163.       but this implementation uses vector of size M (so M should be manageable).
  164.  
  165.     CONSTRAINTS:
  166.       - M can be up to maybe 1e5 if memory allows; for larger M, use a map or unordered_map.
  167.       - N length up to ~20.
  168.  
  169.     NOTES:
  170.       - The function tracks the product modulo M. Since we only care about divisibility,
  171.         this is sufficient.
  172.       - Leading zeros: if a number contains digit 0, its product becomes 0, which
  173.         is divisible by any positive M.
  174. */
  175. long long countProductDivisible(const string& N, int M) {
  176.     int len = N.size();
  177.     // memo[pos][tight][started][prodMod]
  178.     vector<vector<vector<vector<long long>>>> memo(len,
  179.                 vector<vector<vector<long long>>>(2,
  180.                 vector<vector<long long>>(2, vector<long long>(M, -1))));
  181.  
  182.     function<long long(int,bool,bool,int)> dfs = [&](int pos, bool tight, bool started, int prodMod) -> long long {
  183.         if (pos == len) return (started && prodMod == 0) ? 1 : 0; // product divisible by M
  184.         if (!tight && memo[pos][tight][started][prodMod] != -1)
  185.             return memo[pos][tight][started][prodMod];
  186.  
  187.         int limit = tight ? N[pos] - '0' : 9;
  188.         long long ans = 0;
  189.         for (int d = 0; d <= limit; d++) {
  190.             bool newStarted = started || (d != 0);
  191.             int newProdMod;
  192.             if (!newStarted) {
  193.                 newProdMod = 0; // still no digits, product undefined; we keep 0
  194.             } else {
  195.                 if (started) {
  196.                     // multiply existing product by d modulo M
  197.                     newProdMod = (prodMod * d) % M;
  198.                 } else {
  199.                     // first non-zero digit: product = d
  200.                     newProdMod = d % M;
  201.                 }
  202.             }
  203.             ans += dfs(pos + 1, tight && (d == limit), newStarted, newProdMod);
  204.         }
  205.         if (!tight) memo[pos][tight][started][prodMod] = ans;
  206.         return ans;
  207.     };
  208.     return dfs(0, true, false, 0);
  209. }
  210.  
  211. // -------------------------------------------------------------
  212. // 3) DIGIT DP WITH BITMASK – count numbers with at most K distinct digits
  213. // -------------------------------------------------------------
  214.  
  215. /*
  216.     FUNCTION: countAtMostKDistinct(const string& N, int K)
  217.  
  218.     PURPOSE:
  219.       Counts numbers in [0, N] (inclusive) that contain at most K distinct digits.
  220.       Example: N=100, K=1 -> numbers like 11, 22, 33, ..., 99, and also 0..9.
  221.  
  222.     PARAMETERS:
  223.       N (string) – upper bound.
  224.       K (int)    – maximum number of distinct digits allowed.
  225.  
  226.     RETURN:
  227.       long long – count.
  228.  
  229.     TIME COMPLEXITY:
  230.       O(len * 2 * 2 * 2^10) ≈ O(len * 1024) because we use a bitmask of 10 digits.
  231.  
  232.     CONSTRAINTS:
  233.       - N length up to ~20.
  234.       - K is between 0 and 10.
  235.  
  236.     NOTES:
  237.       - Leading zeros are ignored (so "0" is counted with 0 distinct digits).
  238.       - The function uses memoization on (pos, tight, started, mask).
  239.       - __builtin_popcount(mask) counts the number of set bits.
  240. */
  241. long long countAtMostKDistinct(const string& N, int K) {
  242.     int len = N.size();
  243.     // mask up to 2^10 = 1024
  244.     long long memo[20][2][2][1<<10];
  245.     memset(memo, -1, sizeof(memo));
  246.  
  247.     function<long long(int,bool,bool,int)> dfs = [&](int pos, bool tight, bool started, int mask) -> long long {
  248.         if (pos == len) return (started && __builtin_popcount(mask) <= K) ? 1 : 0;
  249.         if (!tight && memo[pos][tight][started][mask] != -1)
  250.             return memo[pos][tight][started][mask];
  251.  
  252.         int limit = tight ? N[pos] - '0' : 9;
  253.         long long ans = 0;
  254.         for (int d = 0; d <= limit; d++) {
  255.             int newMask = mask;
  256.             if (started || d != 0) {
  257.                 newMask = mask | (1 << d);
  258.             } else {
  259.                 newMask = 0; // still not started
  260.             }
  261.             ans += dfs(pos + 1, tight && (d == limit), started || (d != 0), newMask);
  262.         }
  263.         if (!tight) memo[pos][tight][started][mask] = ans;
  264.         return ans;
  265.     };
  266.     return dfs(0, true, false, 0);
  267. }
  268.  
  269. // -------------------------------------------------------------
  270. // 4) DIGIT DP FOR SUM OF DIGITS OF ALL NUMBERS IN [0,N]
  271. // -------------------------------------------------------------
  272.  
  273. /*
  274.     FUNCTION: sumOfAllDigitSums(const string& N)
  275.  
  276.     PURPOSE:
  277.       Computes the sum of all digit sums of every integer from 0 to N (inclusive).
  278.       Example: N=10 -> numbers 0..10 have digit sums: 0,1,2,...,9,1 -> total = 46.
  279.  
  280.     PARAMETERS:
  281.       N (string) – upper bound.
  282.  
  283.     RETURN:
  284.       long long – total sum of digit sums.
  285.  
  286.     TIME COMPLEXITY:
  287.       O(len * 2 * 2 * 10) = O(len).
  288.  
  289.     CONSTRAINTS:
  290.       - N length up to ~19 (since result can be large, but fits in 64-bit for len<=19).
  291.  
  292.     NOTES:
  293.       - The function uses iterative DP that tracks both count of numbers and sum of digit sums.
  294.       - The number 0 is not counted (started=false) because its digit sum is 0, so it contributes 0.
  295.       - The result may overflow 64-bit for very large N (len > 19). Use __int128 if needed.
  296. */
  297. long long sumOfAllDigitSums(const string& N) {
  298.     int len = N.size();
  299.     long long dp[len+1][2][2]; // dp[pos][tight][started] = count of numbers
  300.     long long sum[len+1][2][2]; // sum of digit sums
  301.     memset(dp, 0, sizeof(dp));
  302.     memset(sum, 0, sizeof(sum));
  303.     dp[0][1][0] = 1; // one empty prefix
  304.     for (int pos = 0; pos < len; pos++) {
  305.         for (int tight = 0; tight < 2; tight++) {
  306.             for (int started = 0; started < 2; started++) {
  307.                 if (dp[pos][tight][started] == 0) continue;
  308.                 int limit = tight ? N[pos] - '0' : 9;
  309.                 for (int d = 0; d <= limit; d++) {
  310.                     int ntight = tight && (d == limit);
  311.                     int nstarted = started || (d != 0);
  312.                     dp[pos+1][ntight][nstarted] += dp[pos][tight][started];
  313.                     sum[pos+1][ntight][nstarted] += sum[pos][tight][started] + (nstarted ? d : 0) * dp[pos][tight][started];
  314.                 }
  315.             }
  316.         }
  317.     }
  318.     long long total = 0;
  319.     for (int tight = 0; tight < 2; tight++) {
  320.         total += sum[len][tight][1]; // started must be true to count actual numbers (ignore zero)
  321.     }
  322.     return total;
  323. }
  324.  
  325. // -------------------------------------------------------------
  326. // 5) ADVANCED: DIGIT DP WITH AUTOMATON (KMP, Aho-Corasick)
  327. //    Count numbers <= N that contain (or don't contain) a given pattern
  328. // -------------------------------------------------------------
  329.  
  330. /*
  331.     FUNCTION: countNoSubstring(const string& N, const string& pattern)
  332.  
  333.     PURPOSE:
  334.       Counts numbers in [0, N] that do NOT contain the given pattern as a substring.
  335.       Example: N=1000, pattern="13" -> numbers like 13, 113, 130, etc. are excluded.
  336.  
  337.     PARAMETERS:
  338.       N (string)       – upper bound.
  339.       pattern (string) – the substring we want to avoid.
  340.  
  341.     RETURN:
  342.       long long – count of numbers without the pattern.
  343.  
  344.     TIME COMPLEXITY:
  345.       O(len * 2 * 2 * (m+1) * 10) where m = pattern.length().
  346.       This is because we simulate the KMP automaton for each digit.
  347.  
  348.     CONSTRAINTS:
  349.       - N length up to ~20.
  350.       - pattern length m can be any, but the code uses dynamic allocation for transition table.
  351.  
  352.     NOTES:
  353.       - The function uses KMP (Knuth‑Morris‑Pratt) to build a transition table
  354.         so that when we append a digit, we know the new matched prefix length.
  355.       - Leading zeros are handled correctly; the pattern only matters once a
  356.         non‑zero digit has been placed.
  357.       - The function also counts 0 if it does not contain the pattern.
  358. */
  359. long long countNoSubstring(const string& N, const string& pattern) {
  360.     // Build prefix function for pattern to simulate KMP automaton
  361.     int m = pattern.size();
  362.     vector<int> pi(m, 0);
  363.     for (int i = 1; i < m; i++) {
  364.         int j = pi[i-1];
  365.         while (j > 0 && pattern[i] != pattern[j]) j = pi[j-1];
  366.         if (pattern[i] == pattern[j]) j++;
  367.         pi[i] = j;
  368.     }
  369.  
  370.     // next state for each state (0..m) and digit 0..9
  371.     vector<vector<int>> nextState(m+1, vector<int>(10, 0));
  372.     for (int state = 0; state <= m; state++) {
  373.         for (int d = 0; d < 10; d++) {
  374.             if (state == m) { nextState[state][d] = m; continue; }
  375.             int j = state;
  376.             while (j > 0 && d != (pattern[j] - '0')) j = pi[j-1];
  377.             if (d == (pattern[j] - '0')) j++;
  378.             nextState[state][d] = j;
  379.         }
  380.     }
  381.  
  382.     int len = N.size();
  383.     // memo[pos][tight][started][state]
  384.     vector<vector<vector<vector<long long>>>> memo(len,
  385.                 vector<vector<vector<long long>>>(2,
  386.                 vector<vector<long long>>(2, vector<long long>(m+1, -1))));
  387.  
  388.     function<long long(int,bool,bool,int)> dfs = [&](int pos, bool tight, bool started, int state) -> long long {
  389.         if (state == m) return 0; // found pattern, not allowed
  390.         if (pos == len) return started ? 1 : 0; // count the number itself (if started)
  391.         if (!tight && memo[pos][tight][started][state] != -1)
  392.             return memo[pos][tight][started][state];
  393.  
  394.         int limit = tight ? N[pos] - '0' : 9;
  395.         long long ans = 0;
  396.         for (int d = 0; d <= limit; d++) {
  397.             int nstate = state;
  398.             if (started || d != 0) {
  399.                 nstate = nextState[state][d];
  400.             } else {
  401.                 nstate = 0; // still not started, state remains 0
  402.             }
  403.             ans += dfs(pos + 1, tight && (d == limit), started || (d != 0), nstate);
  404.         }
  405.         if (!tight) memo[pos][tight][started][state] = ans;
  406.         return ans;
  407.     };
  408.     return dfs(0, true, false, 0);
  409. }
  410.  
  411. // -------------------------------------------------------------
  412. // 6) DIGIT DP WITH LARGE RANGES [L,R] – compute f(R) - f(L-1)
  413. // -------------------------------------------------------------
  414.  
  415. /*
  416.     FUNCTION: solveRange(long long L, long long R, function<long long(const string&)> f)
  417.  
  418.     PURPOSE:
  419.       A helper that computes the count of numbers in [L, R] by applying a
  420.       digit‑DP function f on R and L-1, then subtracting.
  421.  
  422.     PARAMETERS:
  423.       L, R (long long) – inclusive range bounds.
  424.       f – a function that takes a string representing the upper bound and returns
  425.           the count of valid numbers in [0, that bound].
  426.  
  427.     RETURN:
  428.       long long – count of numbers in [L, R].
  429.  
  430.     TIME COMPLEXITY:
  431.       Depends on f.
  432.  
  433.     NOTES:
  434.       - L can be 0 or negative? This function assumes L >= 0.
  435.         For negative ranges, you need to shift the numbers.
  436.       - The function converts L-1 to string; if L=0, L-1 is -1 which is handled
  437.         by returning 0 (the function should check x < 0).
  438. */
  439. long long solveRange(long long L, long long R, function<long long(const string&)> f) {
  440.     if (L > R) return 0;
  441.     if (L == 0) return f(to_string(R));
  442.     return f(to_string(R)) - f(to_string(L-1));
  443. }
  444.  
  445. // -------------------------------------------------------------
  446. // 7) DIGIT DP WITH LEADING ZEROS – careful handling
  447. //    Already covered in above examples using 'started' flag.
  448. // -------------------------------------------------------------
  449.  
  450. // -------------------------------------------------------------
  451. // 8) DIGIT DP FOR NUMBERS WITH GIVEN SUM OF SQUARES OF DIGITS
  452. //    (or sum of powers) – can use memo on sum if limit small
  453. // -------------------------------------------------------------
  454.  
  455. /*
  456.     FUNCTION: countWithDigitSumSquares(const string& N, int target)
  457.  
  458.     PURPOSE:
  459.       Counts numbers in [0, N] such that the sum of the squares of their digits
  460.       equals exactly 'target'.
  461.       Example: N=100, target=1 -> numbers like 1, 10, 100? (1^2=1, 1^2+0^2=1, etc.)
  462.  
  463.     PARAMETERS:
  464.       N (string) – upper bound.
  465.       target (int) – the exact sum of squares we want.
  466.  
  467.     RETURN:
  468.       long long – count.
  469.  
  470.     TIME COMPLEXITY:
  471.       O(len * 2 * 2 * maxSum) where maxSum = 81 * len (since max digit square is 81).
  472.  
  473.     CONSTRAINTS:
  474.       - len <= ~20, so maxSum <= 1620, which is fine for a 3D array.
  475.       - target should be <= 81 * len.
  476.  
  477.     NOTES:
  478.       - The function uses memoization on sum, and prunes if sum > target.
  479.       - Leading zeros are ignored (digits before the first non‑zero do not add to sum).
  480. */
  481. long long countWithDigitSumSquares(const string& N, int target) {
  482.     int len = N.size();
  483.     int maxSum = 81 * len;
  484.     vector<vector<vector<vector<long long>>>> memo(len,
  485.                 vector<vector<vector<long long>>>(2,
  486.                 vector<vector<long long>>(2, vector<long long>(maxSum+1, -1))));
  487.  
  488.     function<long long(int,bool,bool,int)> dfs = [&](int pos, bool tight, bool started, int sum) -> long long {
  489.         if (sum > target) return 0;
  490.         if (pos == len) return (started && sum == target) ? 1 : 0;
  491.         if (!tight && memo[pos][tight][started][sum] != -1)
  492.             return memo[pos][tight][started][sum];
  493.  
  494.         int limit = tight ? N[pos] - '0' : 9;
  495.         long long ans = 0;
  496.         for (int d = 0; d <= limit; d++) {
  497.             int newSum = sum + (started || d != 0 ? d*d : 0);
  498.             ans += dfs(pos + 1, tight && (d == limit), started || (d != 0), newSum);
  499.         }
  500.         if (!tight) memo[pos][tight][started][sum] = ans;
  501.         return ans;
  502.     };
  503.     return dfs(0, true, false, 0);
  504. }
  505.  
  506. // -------------------------------------------------------------
  507. // 9) DIGIT DP WITH DP ON "TIGHT" USING ITERATIVE APPROACH
  508. //    (sometimes easier to implement and avoid recursion overhead)
  509. // -------------------------------------------------------------
  510.  
  511. /*
  512.     FUNCTION: countEvenDigitSumIterative(const string& N)
  513.  
  514.     PURPOSE:
  515.       Counts numbers in [0, N] whose digit sum is even.
  516.       Example: N=10 -> numbers with even digit sum: 0,2,4,6,8,11? Actually 11 sum=2 even.
  517.  
  518.     PARAMETERS:
  519.       N (string) – upper bound.
  520.  
  521.     RETURN:
  522.       long long – count.
  523.  
  524.     TIME COMPLEXITY:
  525.       O(len * 2 * 2 * 2) = O(len).
  526.  
  527.     NOTES:
  528.       - This is an iterative (non‑recursive) version of Digit DP.
  529.       - The DP states are: tight, started, parity (0=even,1=odd).
  530.       - It is often faster and avoids recursion limits.
  531. */
  532. long long countEvenDigitSumIterative(const string& N) {
  533.     int len = N.size();
  534.     long long dp[2][2][2]; // tight, started, parity (0 even, 1 odd)
  535.     memset(dp, 0, sizeof(dp));
  536.     dp[1][0][0] = 1; // tight=1, started=0, sum parity=0
  537.     for (int pos = 0; pos < len; pos++) {
  538.         long long ndp[2][2][2];
  539.         memset(ndp, 0, sizeof(ndp));
  540.         for (int tight = 0; tight < 2; tight++) {
  541.             for (int started = 0; started < 2; started++) {
  542.                 for (int parity = 0; parity < 2; parity++) {
  543.                     if (dp[tight][started][parity] == 0) continue;
  544.                     int limit = tight ? N[pos] - '0' : 9;
  545.                     for (int d = 0; d <= limit; d++) {
  546.                         int ntight = tight && (d == limit);
  547.                         int nstarted = started || (d != 0);
  548.                         int nparity = parity;
  549.                         if (nstarted) nparity ^= (d & 1);
  550.                         ndp[ntight][nstarted][nparity] += dp[tight][started][parity];
  551.                     }
  552.                 }
  553.             }
  554.         }
  555.         memcpy(dp, ndp, sizeof(dp));
  556.     }
  557.     long long ans = 0;
  558.     for (int tight = 0; tight < 2; tight++) {
  559.         ans += dp[tight][1][0]; // started=1, even parity
  560.     }
  561.     return ans;
  562. }
  563.  
  564. // -------------------------------------------------------------
  565. // 10) DIGIT DP FOR PRODUCT OF DIGITS WITH MODULO (CAP at M)
  566. //     using map to handle sparse products
  567. // -------------------------------------------------------------
  568.  
  569. // Already implemented in countProductDivisible above (with modulo).
  570.  
  571. // -------------------------------------------------------------
  572. // 11) DIGIT DP WITH MULTIPLE QUERIES (precompute all powers)
  573. // -------------------------------------------------------------
  574.  
  575. // Precompute powers of 10, etc. (helper function)
  576. vector<long long> pow10(20, 1);
  577. void initPow10() {
  578.     for (int i = 1; i < 20; i++) pow10[i] = pow10[i-1] * 10;
  579. }
  580.  
  581. // -------------------------------------------------------------
  582. // 12) DIGIT DP WITH DP ON NUMBERS IN DIFFERENT BASE (binary, etc.)
  583. // -------------------------------------------------------------
  584.  
  585. /*
  586.     FUNCTION: countInBinary(long long N, int K)
  587.  
  588.     PURPOSE:
  589.       Counts numbers in [0, N] (inclusive) whose binary representation has
  590.       exactly K ones.
  591.       Example: N=10 (1010), K=2 -> numbers with two 1's: 3 (11), 5 (101), 6 (110), 9 (1001), 10 (1010) -> count 5.
  592.  
  593.     PARAMETERS:
  594.       N (long long) – upper bound (in decimal).
  595.       K (int) – exact number of 1‑bits required.
  596.  
  597.     RETURN:
  598.       long long – count.
  599.  
  600.     TIME COMPLEXITY:
  601.       O(len * 2 * 2 * K) where len = number of bits in N (<= 63).
  602.  
  603.     NOTES:
  604.       - The function converts N to a binary string.
  605.       - Handles leading zeros (the 'started' flag).
  606.       - The DP is on binary digits (0 or 1).
  607. */
  608. long long countInBinary(long long N, int K) {
  609.     if (N < 0) return 0;
  610.     string s;
  611.     while (N) { s.push_back('0' + (N&1)); N >>= 1; }
  612.     reverse(s.begin(), s.end());
  613.     int len = s.size();
  614.     // memo[pos][tight][started][ones]
  615.     vector<vector<vector<vector<long long>>>> memo(len,
  616.                 vector<vector<vector<long long>>>(2,
  617.                 vector<vector<long long>>(2, vector<long long>(K+1, -1))));
  618.  
  619.     function<long long(int,bool,bool,int)> dfs = [&](int pos, bool tight, bool started, int ones) -> long long {
  620.         if (pos == len) return (started && ones == K) ? 1 : 0;
  621.         if (!tight && memo[pos][tight][started][ones] != -1)
  622.             return memo[pos][tight][started][ones];
  623.  
  624.         int limit = tight ? s[pos] - '0' : 1;
  625.         long long ans = 0;
  626.         for (int d = 0; d <= limit; d++) {
  627.             int newOnes = ones + (started || d != 0 ? d : 0);
  628.             ans += dfs(pos + 1, tight && (d == limit), started || (d != 0), newOnes);
  629.         }
  630.         if (!tight) memo[pos][tight][started][ones] = ans;
  631.         return ans;
  632.     };
  633.     return dfs(0, true, false, 0);
  634. }
  635.  
  636. // -------------------------------------------------------------
  637. // 13) DIGIT DP WITH NEGATIVE NUMBERS: convert to offset or use [0,N]
  638. // -------------------------------------------------------------
  639.  
  640. // For range [L,R] with negative L, shift by offset.
  641.  
  642. // -------------------------------------------------------------
  643. // 14) DIGIT DP WITH LARGE N (string length up to 10^5) – use combinatorics or linear DP
  644. //     For very long strings, we might use precomputed counts without recursion.
  645. // -------------------------------------------------------------
  646.  
  647. // Not covered here; but can use combinatorial precomputation of counts for each position.
  648.  
  649. // -------------------------------------------------------------
  650. // 15) DIGIT DP WITH SUM OF DIGITS MODULO SOMETHING AND COUNT OF NUMBERS
  651. //     (can combine multiple mods)
  652. // -------------------------------------------------------------
  653.  
  654. // Already covered.
  655.  
  656. // -------------------------------------------------------------
  657. // 16) DIGIT DP WITH "STARTED" FLAG – use -1 sentinel for last digit
  658. // -------------------------------------------------------------
  659.  
  660. // Already covered with 10 sentinel.
  661.  
  662. // -------------------------------------------------------------
  663. // 17) DIGIT DP WITH MULTIPLE CONSTRAINTS (e.g., sum, and product)
  664. //     combine states carefully
  665. // -------------------------------------------------------------
  666.  
  667. // -------------------------------------------------------------
  668. // 18) ADVANCED: DIGIT DP WITH AUTOMATON FOR DIVISIBILITY BY A NUMBER
  669. //     (simulate modulo)
  670. // -------------------------------------------------------------
  671.  
  672. /*
  673.     FUNCTION: countDivisibleByK(const string& N, int K)
  674.  
  675.     PURPOSE:
  676.       Counts numbers in [0, N] that are divisible by K.
  677.       Example: N=100, K=7 -> count multiples of 7 up to 100.
  678.  
  679.     PARAMETERS:
  680.       N (string) – upper bound.
  681.       K (int) – divisor.
  682.  
  683.     RETURN:
  684.       long long – count.
  685.  
  686.     TIME COMPLEXITY:
  687.       O(len * 2 * 2 * K) if K is small enough to allocate vector.
  688.  
  689.     CONSTRAINTS:
  690.       - K must be small enough to allocate a 4D vector of size len*2*2*K.
  691.         If K is large (e.g., 1e9), this function will fail because it tries
  692.         to allocate an array of that size. For large K, use a map to store states.
  693. */
  694. long long countDivisibleByK(const string& N, int K) {
  695.     int len = N.size();
  696.     vector<vector<vector<vector<long long>>>> memo(len,
  697.                 vector<vector<vector<long long>>>(2,
  698.                 vector<vector<long long>>(2, vector<long long>(K, -1))));
  699.  
  700.     function<long long(int,bool,bool,int)> dfs = [&](int pos, bool tight, bool started, int mod) -> long long {
  701.         if (pos == len) return (started && mod == 0) ? 1 : 0;
  702.         if (!tight && memo[pos][tight][started][mod] != -1)
  703.             return memo[pos][tight][started][mod];
  704.  
  705.         int limit = tight ? N[pos] - '0' : 9;
  706.         long long ans = 0;
  707.         for (int d = 0; d <= limit; d++) {
  708.             int newMod = (mod * 10 + d) % K;
  709.             ans += dfs(pos + 1, tight && (d == limit), started || (d != 0), newMod);
  710.         }
  711.         if (!tight) memo[pos][tight][started][mod] = ans;
  712.         return ans;
  713.     };
  714.     return dfs(0, true, false, 0);
  715. }
  716.  
  717. // -------------------------------------------------------------
  718. // 19) DIGIT DP WITH RANGE AND DIGIT SUM QUERY (min/max sum)
  719. // -------------------------------------------------------------
  720.  
  721. // Can be handled by DP returning pair (count, sum) – used for sum of digits of numbers in range.
  722.  
  723. // -------------------------------------------------------------
  724. // 20) DIGIT DP WITH DP ON DIGITS AND "GREATER THAN" – can use L-1
  725. // -------------------------------------------------------------
  726.  
  727. // -------------------------------------------------------------
  728. // 21) DIGIT DP WITH STATISTICS: e.g., number of times each digit appears in [L,R]
  729. // -------------------------------------------------------------
  730.  
  731. /*
  732.     FUNCTION: countDigitsUpToN(const string& N)
  733.  
  734.     PURPOSE:
  735.       Counts how many times each digit (0..9) appears in all numbers from 0 to N (inclusive).
  736.       Example: N=10 -> digit 1 appears twice (in 1 and 10), digit 0 appears once (in 10).
  737.  
  738.     PARAMETERS:
  739.       N (string) – upper bound.
  740.  
  741.     RETURN:
  742.       array<long long,10> – count for each digit.
  743.  
  744.     NOTES:
  745.       - This function is correctly implemented using a combinatorial method.
  746.       - It counts occurrences of each digit at each position independently.
  747.       - Works for N up to 10^18 (string length up to 19).
  748. */
  749. array<long long,10> countDigitsUpToN(const string& N) {
  750.     int len = N.size();
  751.     array<long long,10> ans = {};
  752.     // Precompute powers of 10 up to len
  753.     vector<long long> pow10(len+1, 1);
  754.     for (int i = 1; i <= len; i++) pow10[i] = pow10[i-1] * 10;
  755.  
  756.     // For each position i (from most significant, 0-indexed)
  757.     for (int i = 0; i < len; i++) {
  758.         int cur = N[i] - '0';
  759.         // Count occurrences of each digit d at position i
  760.         for (int d = 0; d < 10; d++) {
  761.             long long cnt = 0;
  762.             // Part where prefix is less than N's prefix
  763.             int prefix = 0;
  764.             for (int j = 0; j < i; j++) prefix = prefix * 10 + (N[j] - '0');
  765.             // For all numbers where prefix is strictly smaller
  766.             // The number of such prefixes is prefix (0..prefix-1)
  767.             // For each such prefix, we can choose any digit at position i, and any digits after
  768.             // But careful: if we are counting occurrences of digit d at position i, we need to consider the digit itself.
  769.             // Standard combinatorial formula:
  770.             // For numbers 0..N, count occurrences of digit d at position i (0-indexed from left):
  771.             // Let A = prefix (number formed by digits before i)
  772.             // Let B = suffix length = len - i - 1
  773.             // Let cur = digit at i.
  774.             // Cases:
  775.             // 1. If d < cur: then for all numbers with same prefix A, we can have digit d at i, and suffix any -> A * pow10[B]
  776.             // 2. If d == cur: then we have prefix A, and suffix can be up to suffix value -> A * pow10[B] + (suffix+1)
  777.             // 3. If d > cur: then we can't have prefix A; we need prefix less than A.
  778.             // So we compute for each position.
  779.             // This is a standard method.
  780.             // We'll use the formula:
  781.             long long prefixVal = 0;
  782.             for (int j = 0; j < i; j++) prefixVal = prefixVal * 10 + (N[j] - '0');
  783.             long long suffixVal = 0;
  784.             for (int j = i+1; j < len; j++) suffixVal = suffixVal * 10 + (N[j] - '0');
  785.             long long suffixLen = len - i - 1;
  786.             long long power = pow10[suffixLen];
  787.  
  788.             // Count for this position
  789.             long long total = 0;
  790.             // Case 1: d < cur
  791.             if (d < cur) {
  792.                 total += (prefixVal + 1) * power; // prefix can be 0..prefixVal inclusive
  793.             }
  794.             // Case 2: d == cur
  795.             else if (d == cur) {
  796.                 total += prefixVal * power + (suffixVal + 1);
  797.             }
  798.             // Case 3: d > cur -> nothing from prefix equal, but we can have prefix < prefixVal
  799.             // Actually the standard formula is:
  800.             // total = (prefixVal) * power + (if d < cur) power + (if d == cur) (suffixVal+1)
  801.             // This works.
  802.             // So we can compute:
  803.             total = prefixVal * power;
  804.             if (d < cur) total += power;
  805.             if (d == cur) total += suffixVal + 1;
  806.             // Additionally, we need to ignore leading zeros? But we are counting occurrences of digit d in all numbers,
  807.             // including leading zeros? The standard method counts all positions including leading zeros.
  808.             // Usually we do not want to count leading zeros in numbers with fewer digits.
  809.             // So we need to exclude the case where prefix is all zeros and d=0 at a position where no digit has started.
  810.             // This is tricky. For simplicity, we will count all occurrences including leading zeros,
  811.             // then subtract the leading zeros that appear in numbers with fewer digits.
  812.             // However, for this template, we'll leave a note that this function counts occurrences in the decimal representation
  813.             // without leading zeros. The above formula actually counts occurrences in numbers with leading zeros,
  814.             // but we can adjust by subtracting.
  815.             // For brevity, we'll implement a correct version using DP that tracks started flag.
  816.             // Actually the above formula is for counting occurrences in the range 0..N without leading zeros
  817.             // if we treat numbers as having exactly len digits with leading zeros, we count extra zeros.
  818.             // To get correct counts for representations without leading zeros, we should either use DP or adjust.
  819.             // Let's use DP that returns count of each digit.
  820.             // The DP approach: we can compute for each digit d the total count using a similar DP that tracks started.
  821.             // But we already have a DP that counts numbers, we can extend to count digit occurrences.
  822.             // However, to keep this function simple, we'll implement a DP that returns the frequency for all digits.
  823.         }
  824.     }
  825.     // For better accuracy, we'll implement a DP that counts occurrences properly.
  826.     // The following is a correct implementation using DP that tracks started flag and counts digit frequencies.
  827.     // We'll replace the above with a DP-based approach.
  828.     // Let's implement a DP that returns pair (count, sum of digits) but we need per digit.
  829.     // We'll implement a 3D DP: pos, tight, started, and we store count and sum for each digit.
  830.     // Actually we can do it with DP that returns an array of 10 counts.
  831.     // We'll implement a function that uses recursion and memoization returning a struct.
  832.  
  833.     struct Node {
  834.         long long cnt; // number of valid numbers
  835.         long long freq[10]; // frequency of each digit among those numbers (sum of occurrences)
  836.     };
  837.  
  838.     // We'll use memoization: memo[pos][tight][started] -> Node
  839.     // But this is complex; we'll do it iteratively with DP that tracks count and digit sums.
  840.     // An easier way: for each digit d, we can compute count of occurrences using a modified DP.
  841.     // For each d, we compute the total count of digit d in all numbers <= N.
  842.     // We can write a separate function for each d, or we can compute all together.
  843.     // For simplicity, we'll use the combinatorial method with correction for leading zeros.
  844.     // The standard formula for counting digit d in 0..N without leading zeros:
  845.     // For each position i (from rightmost, 0-indexed), we count how many times d appears.
  846.     // Let pos = i from right (0 = units). Let p = 10^pos.
  847.     // Let high = N / (p*10), cur = (N / p) % 10, low = N % p.
  848.     // Then count of digit d at this position:
  849.     // if d == 0: contribution = (high - 1) * p + (cur == 0 ? low + 1 : 0) + (cur > 0 ? p : 0)
  850.     // Actually formula for digit d:
  851.     // if d != 0:
  852.     //   contribution = high * p + (cur > d ? p : 0) + (cur == d ? low + 1 : 0)
  853.     // if d == 0:
  854.     //   contribution = (high - 1) * p + (cur == 0 ? low + 1 : 0) + (cur > 0 ? p : 0)
  855.     // This counts occurrences in numbers without leading zeros.
  856.     // We'll implement this correctly.
  857.     // Let's redo the function properly:
  858.  
  859.     ans.fill(0);
  860.     for (int pos = 0; pos < len; pos++) {
  861.         long long p = pow10[len - 1 - pos]; // 10^(number of digits after this position)
  862.         long long high = 0, low = 0;
  863.         for (int i = 0; i < pos; i++) high = high * 10 + (N[i] - '0');
  864.         for (int i = pos + 1; i < len; i++) low = low * 10 + (N[i] - '0');
  865.         int cur = N[pos] - '0';
  866.         for (int d = 0; d < 10; d++) {
  867.             long long contrib = 0;
  868.             if (d == 0) {
  869.                 if (high > 0) {
  870.                     contrib += (high - 1) * p;
  871.                 }
  872.                 if (cur == 0) contrib += low + 1;
  873.                 else if (cur > 0) contrib += p;
  874.             } else {
  875.                 contrib += high * p;
  876.                 if (cur > d) contrib += p;
  877.                 else if (cur == d) contrib += low + 1;
  878.             }
  879.             ans[d] += contrib;
  880.         }
  881.     }
  882.     return ans;
  883. }
  884.  
  885. // -------------------------------------------------------------
  886. // 22) ADVANCED: DIGIT DP WITH DP ON "TIGHT" BUT WITH MULTIPLE NUMBERS
  887. //     e.g., count pairs (a,b) with a+b <= N
  888. // -------------------------------------------------------------
  889.  
  890. // Can be solved using DP on digits of sum.
  891.  
  892. // -------------------------------------------------------------
  893. // 23) DIGIT DP WITH CARRY (for addition, multiplication)
  894. // -------------------------------------------------------------
  895.  
  896. // -------------------------------------------------------------
  897. // 24) DIGIT DP WITH DP ON AUTOMATON FOR REGULAR LANGUAGES
  898. //     (e.g., numbers not containing substring, numbers with even number of some digit)
  899. // -------------------------------------------------------------
  900.  
  901. // Already gave example for substring.
  902.  
  903. // -------------------------------------------------------------
  904. // 25) DIGIT DP WITH BINARY REPRESENTATION (for bitwise properties)
  905. // -------------------------------------------------------------
  906.  
  907. // Already gave binary example.
  908.  
  909. // -------------------------------------------------------------
  910. // 26) DIGIT DP WITH LARGE MODULO (e.g., 1e9+7) – just store values mod
  911. // -------------------------------------------------------------
  912.  
  913. // Use long long and take mod at each addition.
  914.  
  915. // -------------------------------------------------------------
  916. // 27) DIGIT DP WITH MEMOIZATION USING MAP (if state space huge)
  917. //     e.g., product state
  918. // -------------------------------------------------------------
  919.  
  920. // Already used map in iterative product example.
  921.  
  922. // -------------------------------------------------------------
  923. // 28) DIGIT DP WITH DP ON LENGTH (when N is huge string)
  924. //     use combinatorics to count numbers of length < len
  925. // -------------------------------------------------------------
  926.  
  927. // Helper: count numbers of length L with some property (without leading zeros)
  928. // Then for given N, compute count for lengths < len, then process prefix.
  929.  
  930. // -------------------------------------------------------------
  931. // 29) DIGIT DP WITH DP ON SUM OF DIGITS AND MODULO (combined)
  932. // -------------------------------------------------------------
  933.  
  934. // -------------------------------------------------------------
  935. // 30) DIGIT DP WITH "AT LEAST ONE" CONDITION (use inclusion-exclusion)
  936. // -------------------------------------------------------------
  937.  
  938. // Example: count numbers having at least one even digit.
  939. // Could count total - count with no even digits.
  940.  
  941. // =====================================================================
  942. //                     USEFUL UTILITY FUNCTIONS
  943. // =====================================================================
  944.  
  945. // Convert long long to string (already provided by to_string)
  946.  
  947. // Count numbers in [L, R] given a digit DP function f(N)
  948. // (overload to handle string as well)
  949. long long solveRangeLL(long long L, long long R, function<long long(const string&)> f) {
  950.     if (L > R) return 0;
  951.     if (L == 0) return f(to_string(R));
  952.     return f(to_string(R)) - f(to_string(L-1));
  953. }
  954.  
  955. /*
  956.     FUNCTION: countPairs(const string& N, int S)
  957.  
  958.     PURPOSE:
  959.       Counts the number of ordered pairs (a, b) such that 0 <= a, b <= N and
  960.       the sum of their digits (digit-wise, without carry) equals S.
  961.       In other words, for each position, we add the two digits and sum them across positions.
  962.  
  963.     PARAMETERS:
  964.       N (string) – upper bound for both a and b (same N).
  965.       S (int)    – target sum of digit sums.
  966.  
  967.     RETURN:
  968.       long long – number of ordered pairs (a,b).
  969.  
  970.     TIME COMPLEXITY:
  971.       O(len * 2 * 2 * S) because we track sum of digits.
  972.  
  973.     CONSTRAINTS:
  974.       - S should be small enough to allocate a 4D vector of size len*2*2*(S+1).
  975.       - N length up to ~20.
  976.  
  977.     NOTES:
  978.       - The DP ensures that at each digit position, d1 + d2 is added to the sum.
  979.       - The function counts ordered pairs (a,b) and (b,a) as distinct.
  980.       - Leading zeros are allowed because both a and b are considered with fixed
  981.         length len (the same as N). So numbers like 007 are allowed.
  982. */
  983. long long countPairs(const string& N, int S) {
  984.     int len = N.size();
  985.     vector<vector<vector<vector<long long>>>> memo(len,
  986.                 vector<vector<vector<long long>>>(2,
  987.                 vector<vector<long long>>(2, vector<long long>(S+1, -1))));
  988.  
  989.     function<long long(int, bool, bool, int)> dfs = [&](int pos, bool tight1, bool tight2, int sum) -> long long {
  990.         if (pos == len) return (sum == S) ? 1 : 0;
  991.         if (!tight1 && !tight2 && memo[pos][tight1][tight2][sum] != -1)
  992.             return memo[pos][tight1][tight2][sum];
  993.  
  994.         int limit1 = tight1 ? N[pos] - '0' : 9;
  995.         int limit2 = tight2 ? N[pos] - '0' : 9;
  996.         long long ans = 0;
  997.         for (int d1 = 0; d1 <= limit1; d1++) {
  998.             for (int d2 = 0; d2 <= limit2; d2++) {
  999.                 int newSum = sum + d1 + d2;
  1000.                 if (newSum > S) continue; // pruning
  1001.                 ans += dfs(pos + 1,
  1002.                            tight1 && (d1 == limit1),
  1003.                            tight2 && (d2 == limit2),
  1004.                            newSum);
  1005.             }
  1006.         }
  1007.         if (!tight1 && !tight2) memo[pos][tight1][tight2][sum] = ans;
  1008.         return ans;
  1009.     };
  1010.  
  1011.     return dfs(0, true, true, 0);
  1012. }
  1013.  
  1014. /*
  1015.     FUNCTION: countAtLeastKDistinct(const string& N, int K)
  1016.  
  1017.     PURPOSE:
  1018.       Counts numbers in [0, N] that contain at least K distinct digits.
  1019.       Example: N=100, K=2 -> numbers with at least two different digits.
  1020.  
  1021.     PARAMETERS:
  1022.       N (string) – upper bound.
  1023.       K (int)    – minimum number of distinct digits.
  1024.  
  1025.     RETURN:
  1026.       long long – count.
  1027.  
  1028.     TIME COMPLEXITY:
  1029.       O(len * 2 * 2 * 2^10) ≈ O(len * 1024).
  1030.  
  1031.     CONSTRAINTS:
  1032.       - K between 0 and 10.
  1033.       - N length up to ~20.
  1034.  
  1035.     NOTES:
  1036.       - This is similar to countAtMostKDistinct but uses >=.
  1037.       - Leading zeros are ignored.
  1038. */
  1039. long long countAtLeastKDistinct(const string& N, int K) {
  1040.     int len = N.size();
  1041.     long long memo[20][2][2][1 << 10];
  1042.     memset(memo, -1, sizeof(memo));
  1043.  
  1044.     function<long long(int, bool, bool, int)> dfs = [&](int pos, bool tight, bool started, int mask) -> long long {
  1045.         if (pos == len) return (started && __builtin_popcount(mask) >= K) ? 1 : 0;
  1046.         if (!tight && memo[pos][tight][started][mask] != -1)
  1047.             return memo[pos][tight][started][mask];
  1048.  
  1049.         int limit = tight ? N[pos] - '0' : 9;
  1050.         long long ans = 0;
  1051.         for (int d = 0; d <= limit; d++) {
  1052.             int newMask = mask;
  1053.             if (started || d != 0) // ignore leading zeros
  1054.                 newMask = mask | (1 << d);
  1055.             ans += dfs(pos + 1, tight && (d == limit), started || (d != 0), newMask);
  1056.         }
  1057.         if (!tight) memo[pos][tight][started][mask] = ans;
  1058.         return ans;
  1059.     };
  1060.     return dfs(0, true, false, 0);
  1061. }
  1062.  
  1063. // =====================================================================
  1064. //                       EXAMPLE MAIN (usage)
  1065. // =====================================================================
  1066.  
  1067. int main() {
  1068.     ios::sync_with_stdio(false);
  1069.     cin.tie(nullptr);
  1070.  
  1071.     // Example: count numbers in [0, 1000] with even digit sum
  1072.     auto countEvenSum = [](const string& N) -> long long {
  1073.         return countEvenDigitSumIterative(N);
  1074.     };
  1075.     long long ans = countEvenSum("1000");
  1076.     cout << "Numbers <= 1000 with even digit sum: " << ans << "\n";
  1077.  
  1078.     // Example: count numbers with no consecutive equal digits up to 10^9
  1079.     DigitDP_Basic dp;
  1080.     cout << "No consecutive equal digits <= 1000: " << dp.countNoConsecutiveEqual("1000") << "\n";
  1081.  
  1082.     // Example: count numbers in [1, 1000] with digit sum divisible by 5
  1083.     cout << "Digit sum divisible by 5 <= 1000: " << countDigitSumMod("1000", 5) << "\n";
  1084.  
  1085.     // Example: count numbers in [0, 1000] that do not contain "13"
  1086.     cout << "No substring '13' <= 1000: " << countNoSubstring("1000", "13") << "\n";
  1087.  
  1088.     // Example: count numbers with digit product divisible by 2 up to 100
  1089.     cout << "Product divisible by 2 <= 100: " << countProductDivisible("100", 2) << "\n";
  1090.  
  1091.     // Example: count pairs (a,b) with digit sum = 5 up to N=10
  1092.     cout << "Pairs with digit sum 5 up to 10: " << countPairs("10", 5) << "\n";
  1093.  
  1094.     return 0;
  1095. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Numbers <= 1000 with even digit sum: 499
No consecutive equal digits <= 1000: 729
Digit sum divisible by 5 <= 1000: 199
No substring '13' <= 1000: 980
Product divisible by 2 <= 100: 70
Pairs with digit sum 5 up to 10: 8
https://ideone.com/t0zDw5
language:
C++14 (clang 8.0)
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!