Contar formas de representar N como suma de enteros palindrómicos que no tienen el dígito 1

Dado un entero positivo N , la tarea es encontrar el número de formas distintas de expresar N como una suma de enteros palindrómicos positivos que no tienen el dígito 1 en ellos.

Nota: Como la respuesta puede ser bastante grande, imprímela módulo 10 ⁹ +7 .

Ejemplos:

Entrada: N = 4
Salida: 2
Explicación: Los siguientes son los 2 conjuntos múltiples que cumplen la condición:
1. 2+2 = 4
2. 4 = 4

Entrada: N = 8
Salida: 7
Explicación: Los siguientes son los distintos Multisets que satisfacen la condición:
1. 2+2+2+2 = 8
2. 2+3+3 = 8
3. 2+2+4 = 8
4 4+4 = 8
5. 3+5 = 8
6. 2+6 = 8
7. 8 = 8

Acercarse:

Aquí cada número entero palindrómico que no tiene el dígito 1 puede venir un número infinito de veces. (Se permite la repetición), esto es lo que llamamos Mochila ilimitada . 

• Tenemos 2 opciones para un número palindrómico sin un dígito 1, ya sea i) para incluir, o ii) para excluir. Pero aquí, el proceso de inclusión no es de una sola vez; podemos incluir cualquier número palindrómico sin uno solo cualquier número de veces hasta que N < Suma.
• Básicamente, si estamos en V[m] , podemos tomar tantas instancias de ese número entero (inclusión ilimitada), es decir , count(V, m, sum – V[m])  , luego nos movemos a V[m-1] . Después de pasar a V[m-1] , no podemos retroceder y no podemos hacer elecciones para V[m], es decir , count(V, m-1, sum) .
• Para encontrar el número total de formas, tenemos que sumar estas 2 opciones posibles, es decir, count(V, m, sum – S[m] ) + count(V, m-1, sum ) .

Siga los pasos que se indican a continuación para un mejor enfoque:

• Declare un vector V para almacenar todos los números menores que N que son palíndromos y no contienen el dígito 1 .
• Use una función recursiva y en cada llamada recursiva, pase el vector V y el índice entero (m) y el valor de N (suma) .
• En cada iteración, realice dos llamadas recursivas,  
  • En uno de ellos disminuir m (elemento índice) en 1 y 
  • Por el otro, disminuya el valor de sum en V[m] .
    • Si la suma se convirtió en 0 , devuelve 1 . Entonces se agregará a la respuesta final que devolvemos.
  • Si sum o m es menor que 0 , devuelve 0.

A continuación se muestra la implementación del enfoque anterior.
 

// C++ code to implement the approach
  
#include <bits/stdc++.h>
using namespace std;
  
int mod = 1e9 + 7;
  
// Function for checking if
// the given integer is palindrom or not
bool isPalindrom(int i)
{
    string x = to_string(i);
    int n = x.length();
    int cnt_one = 0;
    for (int i = 0; i < n / 2; i++) {
        if (x[i] == '1') {
            cnt_one++;
        }
        if (x[i] == x[n - 1 - i]) {
            continue;
        }
        else {
            return false;
        }
    }
    if (cnt_one == 1)
        return false;
    return true;
}
  
// Helper function
int helper(vector<int>& V, int m, int sum)
{
    // Base cases
  
    // As there is 1 way which is the empty set
    if (sum == 0)
        return 1;
  
    // If sum is negative then there is no way
    if (sum < 0)
        return 0;
  
    // If no integer left and the sum is not 0
    // then we cannot make sum 0
    if (m < 0 && sum > 0)
        return 0;
  
    return (helper(V, m - 1, sum) % mod
            + helper(V, m, sum - V[m]) % mod)
           % mod;
}
  
// Function to find the count of ways
int countMultiSet(int N)
{
    vector<int> V;
  
    // Vector storing the palindromic number till n
    for (int i = 2; i <= N; i++) {
        if (isPalindrom(i)) {
            V.push_back(i);
        }
    }
  
    // Calling the helper function
    return helper(V, V.size() - 1, N);
}
  
// driver function
int main()
{
    int N = 8;
  
    // calling the function
    cout << countMultiSet(N);
    return 0;
}

7

Complejidad temporal: O(2 ^M ) M es el tamaño del vector V 
Espacio auxiliar: O(M)