Dada una K y una array Q[][] que consta de consultas de la forma {N, M}, la tarea de cada consulta es contar el número de strings posibles de todas las longitudes desde Q[i][0] hasta Q[ i][1] que satisfaga las siguientes propiedades:
- La frecuencia de 0 es igual a un múltiplo de K.
- Se dice que dos strings son diferentes solo si las frecuencias de 0 y 1 son diferentes
Dado que la respuesta puede ser bastante grande, calcule la respuesta por mod 10 9 + 7 .
Ejemplos:
Entrada : K = 3, Q[][] = {{1, 3}}
Salida : 4
Explicación:
Todas las strings posibles de longitud 1: {“1”}
Todas las strings posibles de longitud 2: {“11”}
Todas las posibles strings de longitud 3: {“111”, “000”}
Por lo tanto, se pueden generar un total de 4 strings.Entrada : K = 3, Q[][] = {{1, 4}, {3, 7}}
Salida:
7
24
Enfoque ingenuo:
siga los pasos a continuación para resolver el problema:
- Inicialice una array dp[] tal que dp[i] denote el número de strings posibles de longitud i .
- Inicializar dp[0] = 1.
- Para cada i -ésima Longitud, surgen como máximo dos posibilidades:
- Agregar ‘1’ a las strings de longitud i – 1 .
- Agregue K 0 a todas las strings posibles de longitud iK .
- Finalmente, para cada consulta Q[i] , imprima la suma de todos los dp[j] para Q[i][0] <= j <= Q[i][1].
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(N)
Enfoque eficiente:
el enfoque anterior se puede optimizar utilizando Prefix Sum Array . Siga los pasos a continuación:
- Actualice la array dp[] siguiendo los pasos del enfoque anterior.
- Calcule la array de suma de prefijos de la array dp[] .
- Finalmente, para cada consulta Q[i] , calcule dp[Q[i][1]] – dp[Q[i][0] – 1] e imprima como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int MOD = 1000000007;
long int dp[N];
// Function to calculate the
// count of possible strings
void countStrings(int K,
vector<vector<int> > Q)
{
// Initialize dp[0]
dp[0] = 1;
// dp[i] represents count of
// strings of length i
for (int i = 1; i < N; i++) {
dp[i] = dp[i - 1];
// Add dp[i-k] if i>=k
if (i >= K)
dp[i]
= (dp[i] + dp[i - K]) % MOD;
}
// Update Prefix Sum Array
for (int i = 1; i < N; i++) {
dp[i] = (dp[i] + dp[i - 1]) % MOD;
}
for (int i = 0; i < Q.size(); i++) {
long int ans
= dp[Q[i][1]] - dp[Q[i][0] - 1];
if (ans < 0)
ans = ans + MOD;
cout << ans << endl;
}
}
// Driver Code
int main()
{
int K = 3;
vector<vector<int> > Q
= { { 1, 4 }, { 3, 7 } };
countStrings(K, Q);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static int N = (int)(1e5 + 5);
static int MOD = 1000000007;
static int []dp = new int[N];
// Function to calculate the
// count of possible Strings
static void countStrings(int K, int[][] Q)
{
// Initialize dp[0]
dp[0] = 1;
// dp[i] represents count of
// Strings of length i
for(int i = 1; i < N; i++)
{
dp[i] = dp[i - 1];
// Add dp[i-k] if i>=k
if (i >= K)
dp[i] = (dp[i] + dp[i - K]) % MOD;
}
// Update Prefix Sum Array
for(int i = 1; i < N; i++)
{
dp[i] = (dp[i] + dp[i - 1]) % MOD;
}
for(int i = 0; i < Q.length; i++)
{
int ans = dp[Q[i][1]] - dp[Q[i][0] - 1];
if (ans < 0)
ans = ans + MOD;
System.out.print(ans + "\n");
}
}
// Driver Code
public static void main(String[] args)
{
int K = 3;
int [][]Q = { { 1, 4 }, { 3, 7 } };
countStrings(K, Q);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach N = int(1e5 + 5) MOD = 1000000007 dp = [0] * N # Function to calculate the # count of possible strings def countStrings(K, Q): # Initialize dp[0] dp[0] = 1 # dp[i] represents count of # strings of length i for i in range(1, N): dp[i] = dp[i - 1] # Add dp[i-k] if i>=k if(i >= K): dp[i] = (dp[i] + dp[i - K]) % MOD # Update Prefix Sum Array for i in range(1, N): dp[i] = (dp[i] + dp[i - 1]) % MOD for i in range(len(Q)): ans = dp[Q[i][1]] - dp[Q[i][0] - 1] if (ans < 0): ans += MOD print(ans) # Driver Code K = 3 Q = [ [ 1, 4 ], [ 3, 7 ] ] countStrings(K, Q) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
static int N = (int)(1e5 + 5);
static int MOD = 1000000007;
static int []dp = new int[N];
// Function to calculate the
// count of possible Strings
static void countStrings(int K,
int[,] Q)
{
// Initialize dp[0]
dp[0] = 1;
// dp[i] represents count of
// Strings of length i
for(int i = 1; i < N; i++)
{
dp[i] = dp[i - 1];
// Add dp[i-k] if i>=k
if (i >= K)
dp[i] = (dp[i] +
dp[i - K]) % MOD;
}
// Update Prefix Sum Array
for(int i = 1; i < N; i++)
{
dp[i] = (dp[i] +
dp[i - 1]) % MOD;
}
for(int i = 0; i < Q.GetLength(0); i++)
{
int ans = dp[Q[i, 1]] -
dp[Q[i, 0] - 1];
if (ans < 0)
ans = ans + MOD;
Console.Write(ans + "\n");
}
}
// Driver Code
public static void Main(String[] args)
{
int K = 3;
int [,]Q = {{1, 4}, {3, 7}};
countStrings(K, Q);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
let N = parseInt((1e5 + 5));
let MOD = 1000000007;
let dp = Array(N).fill(0);
// Function to calculate the
// count of possible Strings
function countStrings(K, Q)
{
// Initialize dp[0]
dp[0] = 1;
// dp[i] represents count of
// Strings of length i
for(let i = 1; i < N; i++)
{
dp[i] = dp[i - 1];
// Add dp[i-k] if i>=k
if (i >= K)
dp[i] = (dp[i] + dp[i - K]) % MOD;
}
// Update Prefix Sum Array
for(let i = 1; i < N; i++)
{
dp[i] = (dp[i] + dp[i - 1]) % MOD;
}
for(let i = 0; i < Q.length; i++)
{
var ans = dp[Q[i][1]] - dp[Q[i][0] - 1];
if (ans < 0)
ans = ans + MOD;
document.write(ans + "\n");
}
}
// Driver Code
var K = 3;
let Q = [ [ 1, 4 ], [ 3, 7 ] ];
countStrings(K, Q);
// This code is contributed by gauravrajput1
</script>
Producción:
7 24
Complejidad temporal: O(N + Q)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nishitsharma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA