fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>  // For memset
  4. typedef long long ll;
  5. using namespace std;
  6.  
  7. const int MAX_K = 5;
  8. const int MAX_LAST_K = 10000;  // 10^(K - 1)
  9. const int MAX_DIGIT = 10;
  10.  
  11. bool hasPalindrome[MAX_LAST_K][MAX_DIGIT];
  12.  
  13. void calculateHasPalindromeTable() {
  14.     for (int lastK = 0; lastK < MAX_LAST_K; ++lastK) {
  15.         vector<int> lastKDigits(MAX_K - 1);
  16.  
  17.         int temp = lastK;
  18.         for (int i = MAX_K - 2; i >= 0; --i) {
  19.             lastKDigits[i] = temp % 10;
  20.             temp /= 10;
  21.         }
  22.  
  23.         for (int digit = 0; digit < MAX_DIGIT; ++digit) {
  24.             vector<int> newLastKDigits = lastKDigits;
  25.             newLastKDigits.push_back(digit);
  26.             bool foundPalindrome = false;
  27.             int n = newLastKDigits.size();
  28.             for (int l = 2; l <= MAX_K && l <= n; ++l) {
  29.                 bool isPalindrome = true;
  30.                 for (int i = 0; i < l / 2; ++i) {
  31.                     if (newLastKDigits[n - l + i] != newLastKDigits[n - i - 1]) {
  32.                         isPalindrome = false;
  33.                         break;
  34.                     }
  35.                 }
  36.                 if (isPalindrome) {
  37.                     foundPalindrome = true;
  38.                     break;
  39.                 }
  40.             }
  41.             hasPalindrome[lastK][digit] = foundPalindrome;
  42.         }
  43.     }
  44. }
  45.  
  46. ll dp[20][MAX_LAST_K][2][2];
  47. string numberString;
  48.  
  49. void initializeDP() {
  50.     memset(dp, -1, sizeof(dp));
  51. }
  52.  
  53. ll solveDp(int position, int lastK, bool tight, bool leadingZero) {
  54.     if (position == numberString.length()) {
  55.         return leadingZero ? 0 : 1;
  56.     }
  57.  
  58.     int tightIndex = tight ? 1 : 0;
  59.     int leadingZeroIndex = leadingZero ? 1 : 0;
  60.  
  61.     if (dp[position][lastK][tightIndex][leadingZeroIndex] != -1) {
  62.         return dp[position][lastK][tightIndex][leadingZeroIndex];
  63.     }
  64.  
  65.     int limit = tight ? numberString[position] - '0' : 9;
  66.     ll result = 0;
  67.     for (int digit = 0; digit <= limit; ++digit) {
  68.         bool newTight = tight && (digit == limit);
  69.         bool nextLeadingZero = leadingZero && (digit == 0);
  70.         if (nextLeadingZero) {
  71.             result += solveDp(position + 1, lastK, newTight, nextLeadingZero);
  72.         } else {
  73.             if (hasPalindrome[lastK][digit]) {
  74.                 continue;  // Skip if adding 'digit' forms a palindrome
  75.             }
  76.             int newLastK = (lastK * 10 + digit) % MAX_LAST_K;
  77.             result += solveDp(position + 1, newLastK, newTight, false);
  78.         }
  79.     }
  80.     dp[position][lastK][tightIndex][leadingZeroIndex] = result;
  81.     return result;
  82. }
  83.  
  84. ll countPalinFree(ll n) {
  85.     if (n < 0) return 0;
  86.     numberString = to_string(n);
  87.     initializeDP();
  88.     return solveDp(0, 0, true, true);
  89. }
  90.  
  91. int main() {
  92.     ll a, b;
  93.     cin >> a >> b;
  94.  
  95.     calculateHasPalindromeTable();
  96.  
  97.     ll result;
  98.     if (a == 0) {
  99.         result = countPalinFree(b);
  100.     } else {
  101.         result = countPalinFree(b) - countPalinFree(a - 1);
  102.     }
  103.     cout << result << endl;
  104.  
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0.01s 9960KB
comments (?)
stdin
copy 
11032505 10912606
stdout
copy 
0
https://ideone.com/BtIhRY
language:
C++14 (gcc 8.3)
created:
4 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!