Suma de Dígitos de las Buenas Strings

Una string se dice buena si está hecha con solo dígitos del 0 al 9 y los elementos adyacentes son diferentes. La tarea es encontrar la suma de los dígitos de todas las posibles strings buenas de longitud X que terminan con el dígito Y dado . La respuesta podría ser grande, así que imprima la respuesta módulo 10 9 + 7 .

Ejemplos:  

Entrada: X = 2, Y = 2 
Salida: 61 
Todas las strings posibles de longitud 2 que terminan en 2 son: 
02, 12, 32, 42, 52, 62, 72, 82, 92. 
Ahora, ((0 + 2) + (1 + 2) + (3 + 2) + (4 + 2) + (5 + 2) 
+ (6 + 2) + (7 + 2) + (8 + 2) + (9 + 2)) = 61

Entrada: X = 6, Y = 4 
Salida: 1567751 

Enfoque: Este problema se puede resolver usando programación dinámica . Definamos los siguientes estados:  

  1. dp[i][j]: Suma de los dígitos de todas las posibles strings buenas de longitud i que terminan en j .
  2. cnt[i][j]: cuenta las strings buenas de longitud i que terminan en j .

El valor del estado anterior deberá usarse para calcular el valor del estado actual, ya que los dígitos adyacentes deben compararse para determinar si son iguales o no. Ahora, la relación de recurrencia será:  

dp[i][j] = dp[i][j] + dp[i – 1][k] + cnt[i – 1][k] * j

 Aquí, dp[i – 1][k] es la suma de los dígitos de buenas strings de longitud (i – 1) que terminan en k y k != j
cnt[i -1][k] es el conteo de buenas strings de longitud (i – 1) que terminan en k y k != j
Entonces, para la posición i , se debe agregar (cnt(i – 1)[k] * j) ya que j se coloca en el índice i y el recuento de strings posibles que tienen una longitud (i – 1) es cnt[i – 1 ][k] .
A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define DIGITS 10
#define MAX 10000
#define MOD 1000000007
 
// To store the states of the dp
long dp[MAX][DIGITS], cnt[MAX][DIGITS];
 
// Function to fill the dp table
void precompute()
{
 
    // dp[i][j] : Sum of the digits of all
    // possible good strings of length
    // i that end with j
    // cnt[i][j] : Count of the good strings
    // of length i that end with j
 
    // Sum of digits of the string of length
    // 1 is i as i is only number in that string
    // and count of good strings of length 1
    // that end with i is also 1
    for (int i = 0; i < DIGITS; i++)
        dp[1][i] = i, cnt[1][i] = 1;
 
    for (int i = 2; i < MAX; i++) {
        for (int j = 0; j < DIGITS; j++) {
            for (int k = 0; k < DIGITS; k++) {
 
                // Adjacent digits are different
                if (j != k) {
                    dp[i][j] = dp[i][j]
                               + (dp[i - 1][k] + (cnt[i - 1][k] * j) % MOD)
                                     % MOD;
                    dp[i][j] %= MOD;
 
                    // Increment the count as digit at
                    // (i - 1)'th index is k and count
                    // of good strings is equal to this
                    // because at the end of the strings of
                    // length (i - 1) we are just
                    // putting digit j as the last digit
                    cnt[i][j] += cnt[i - 1][k];
                    cnt[i][j] %= MOD;
                }
            }
        }
    }
}
 
// Driver code
int main()
{
    long long int x = 6, y = 4;
 
    precompute();
 
    cout << dp[x][y];
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
    final static int DIGITS = 10;
    final static int MAX = 10000;
    final static int MOD = 1000000007;
     
    // To store the states of the dp
    static int dp[][] = new int[MAX][DIGITS];
    static int cnt[][] = new int[MAX][DIGITS];
     
    // Function to fill the dp table
    static void precompute()
    {
     
        // dp[i][j] : Sum of the digits of all
        // possible good strings of length
        // i that end with j
        // cnt[i][j] : Count of the good strings
        // of length i that end with j
     
        // Sum of digits of the string of length
        // 1 is i as i is only number in that string
        // and count of good strings of length 1
        // that end with i is also 1
        for (int i = 0; i < DIGITS; i++)
        {
            dp[1][i] = i;
            cnt[1][i] = 1;
        }
     
        for (int i = 2; i < MAX; i++)
        {
            for (int j = 0; j < DIGITS; j++)
            {
                for (int k = 0; k < DIGITS; k++)
                {
     
                    // Adjacent digits are different
                    if (j != k)
                    {
                        dp[i][j] = dp[i][j] + (dp[i - 1][k] +
                                             (cnt[i - 1][k] * j) % MOD)
                                                                 % MOD;
                        dp[i][j] %= MOD;
     
                        // Increment the count as digit at
                        // (i - 1)'th index is k and count
                        // of good strings is equal to this
                        // because at the end of the strings of
                        // length (i - 1) we are just
                        // putting digit j as the last digit
                        cnt[i][j] += cnt[i - 1][k];
                        cnt[i][j] %= MOD;
                    }
                }
            }
        }
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int x = 6, y = 4;
     
        precompute();
     
        System.out.println(dp[x][y]);
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation of the approach
DIGITS = 10;
MAX = 10000;
MOD = 1000000007;
 
# To store the states of the dp
dp = [[0 for i in range(DIGITS)]
         for i in range(MAX)];
cnt = [[0 for i in range(DIGITS)]
          for i in range(MAX)];
 
# Function to fill the dp table
def precompute():
 
    # dp[i][j] : Sum of the digits of all
    # possible good strings of length
    # i that end with j
    # cnt[i][j] : Count of the good strings
    # of length i that end with j
 
    # Sum of digits of the string of length
    # 1 is i as i is only number in that string
    # and count of good strings of length 1
    # that end with i is also 1
    for i in range(DIGITS):
     
        dp[1][i] = i;
        cnt[1][i] = 1;
     
    for i in range(2, MAX):
        for j in range(DIGITS):
            for k in range(DIGITS):
                 
                # Adjacent digits are different
                if (j != k):
                 
                    dp[i][j] = dp[i][j] + (dp[i - 1][k] +\
                                         (cnt[i - 1][k] * j) % MOD) % MOD;
                    dp[i][j] %= MOD;
 
                    # Increment the count as digit at
                    # (i - 1)'th index is k and count
                    # of good strings is equal to this
                    # because at the end of the strings of
                    # length (i - 1) we are just
                    # putting digit j as the last digit
                    cnt[i][j] += cnt[i - 1][k];
                    cnt[i][j] %= MOD;
 
# Driver code
x = 6; y = 4;
 
precompute();
 
print(dp[x][y]);
 
# This code is contributed by 29AjayKumar

C#

// C# implementation of the approach
using System;
     
class GFG
{
    readonly static int DIGITS = 10;
    readonly static int MAX = 10000;
    readonly static int MOD = 1000000007;
     
    // To store the states of the dp
    static int [,]dp = new int[MAX, DIGITS];
    static int [,]cnt = new int[MAX, DIGITS];
     
    // Function to fill the dp table
    static void precompute()
    {
     
        // dp[i][j] : Sum of the digits of all
        // possible good strings of length
        // i that end with j
        // cnt[i][j] : Count of the good strings
        // of length i that end with j
     
        // Sum of digits of the string of length
        // 1 is i as i is only number in that string
        // and count of good strings of length 1
        // that end with i is also 1
        for (int i = 0; i < DIGITS; i++)
        {
            dp[1, i] = i;
            cnt[1, i] = 1;
        }
     
        for (int i = 2; i < MAX; i++)
        {
            for (int j = 0; j < DIGITS; j++)
            {
                for (int k = 0; k < DIGITS; k++)
                {
     
                    // Adjacent digits are different
                    if (j != k)
                    {
                        dp[i, j] = dp[i, j] + (dp[i - 1, k] +
                                             (cnt[i - 1, k] * j) % MOD)
                                                                 % MOD;
                        dp[i, j] %= MOD;
     
                        // Increment the count as digit at
                        // (i - 1)'th index is k and count
                        // of good strings is equal to this
                        // because at the end of the strings of
                        // length (i - 1) we are just
                        // putting digit j as the last digit
                        cnt[i, j] += cnt[i - 1, k];
                        cnt[i, j] %= MOD;
                    }
                }
            }
        }
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int x = 6, y = 4;
     
        precompute();
     
        Console.WriteLine(dp[x,y]);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the approach
 
var DIGITS = 10
var MAX = 10000
var MOD = 1000000007
 
// To store the states of the dp
var dp = Array.from(Array(MAX), ()=> Array(DIGITS).fill(0));
var cnt = Array.from(Array(MAX), ()=> Array(DIGITS).fill(0));
 
// Function to fill the dp table
function precompute()
{
 
    // dp[i][j] : Sum of the digits of all
    // possible good strings of length
    // i that end with j
    // cnt[i][j] : Count of the good strings
    // of length i that end with j
 
    // Sum of digits of the string of length
    // 1 is i as i is only number in that string
    // and count of good strings of length 1
    // that end with i is also 1
    for (var i = 0; i < DIGITS; i++)
        dp[1][i] = i, cnt[1][i] = 1;
 
    for (var i = 2; i < MAX; i++) {
        for (var j = 0; j < DIGITS; j++) {
            for (var k = 0; k < DIGITS; k++) {
 
                // Adjacent digits are different
                if (j != k) {
                    dp[i][j] = dp[i][j]
                               + (dp[i - 1][k] +
                                  (cnt[i - 1][k] * j) % MOD)% MOD;
                    dp[i][j] %= MOD;
 
                    // Increment the count as digit at
                    // (i - 1)'th index is k and count
                    // of good strings is equal to this
                    // because at the end of the strings of
                    // length (i - 1) we are just
                    // putting digit j as the last digit
                    cnt[i][j] += cnt[i - 1][k];
                    cnt[i][j] %= MOD;
                }
            }
        }
    }
}
 
// Driver code
var x = 6, y = 4;
precompute();
document.write( dp[x][y]);
 
 
</script>
Producción: 

1567751

 

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(10 5 )
 

Publicación traducida automáticamente

Artículo escrito por souradeep y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *