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)) = 61Entrada: X = 6, Y = 4
Salida: 1567751
Enfoque: Este problema se puede resolver usando programación dinámica . Definamos los siguientes estados:
- dp[i][j]: Suma de los dígitos de todas las posibles strings buenas de longitud i que terminan en j .
- 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 )