Recuento de la suma de «10» subsecuencias para cada 1 en la string con A 1, B 10 y C 0

Dado un A « 1″, B «10» y C «0», la tarea es contar la suma de «10» subsecuencias para cada 1 en la string con A 1, B 10 y C 0 .

Ejemplos:

Entrada: A = 1, B = 2, C = 3
Salida: 14
Explicación: A = 1 significa una vez «1» string, B = 2 significa dos veces «10» strings, y C = 3 significa tres veces «0» instrumentos de cuerda. 
Después de la concatenación, la string formada es «11010000» . 
Entonces, para el 1er «1», son posibles cinco subsecuencias «10»,  
     para el 2do «1» son posibles cinco subsecuencias «10», y
     para el 3er «1» son posibles cuatro subsecuencias «10». 
Por lo tanto, un total de 5 + 5 + 4 = 14 subsecuencias son posibles.

Entrada: A = 0, B = 0, C = 1
Salida: 0
Explicación: A = 0 significa que no hay una string «1», B = 0 significa que no hay una string «10» y C = 1 significa una string «0». 
Entonces, la string final es «0» . 
Por lo tanto, no es posible una subsecuencia «10» y, por lo tanto, la salida es 0.

Enfoque ingenuo: la solución más simple para este problema es generar la string y luego, para cada 1, encontrar la cantidad de «10» subsecuencias posibles. Devuelve la suma de la cuenta de todas esas subsecuencias al final.

Complejidad de tiempo: O(N*countOf1s)
Espacio auxiliar: O(1)

Enfoque Eficiente: La idea de resolver el problema de manera eficiente utilizando algunos conceptos básicos de matemáticas y combinatorias .

• Para obtener la subsecuencia máxima, agregue todos los «1» al comienzo de la string final y «0» al final de la string final.
• Declare ans variable y almacene el conteo de la posible forma de subsecuencia «10» por A por «1» y B por «10» multiplicando (A*B)+((B*(B+1))/2).
• Sume respuestas con el conteo de posibles subsecuencias «10» por C por «0» y A y B por «1» multiplicando (A*B)*C .
• Módulo de retorno de respuesta.

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

// C++ Code for the above approach:
 
#include <iostream>
using namespace std;
int maxsubsequence(int A, int B, int C)
{
 
    // As the answer may be very large,
    // Find it modulo 109 + 7
    long long mod = 1e9 + 7;
 
    // Count possible subsequence by
    // A times"1" and B times"10"
    long long ans
        = (A * 1l * B) % mod
          + ((B * 1l * (B + 1)) / 2) % mod;
    if (ans >= mod) {
        ans -= mod;
    }
 
    // Count possible subsequence
    // By C times "0" and A & B time  "1"
    ans += ((A + B) * 1l * C) % mod;
    if (ans >= mod) {
        ans -= mod;
    }
    return ans;
}
 
// Driver code
int main()
{
    int A = 1, B = 2, C = 3;
    cout << maxsubsequence(A, B, C) << endl;
    return 0;
}

// JAVA Code for the above approach:
 
import java.util.*;
class GFG {
  public static int maxsubsequence(int A, int B, int C)
  {
 
    // As the answer may be very large,
    // Find it modulo 109 + 7
    long mod = (long)(1e9 + 7);
 
    // Count possible subsequence by
    // A times"1" and B times"10"
    long ans = (long)(A * B) % mod
      + ((B * (B + 1)) / 2) % mod;
    if (ans >= mod) {
      ans -= mod;
    }
 
    // Count possible subsequence
    // By C times "0" and A & B time  "1"
    ans += ((A + B) * C) % mod;
    if (ans >= mod) {
      ans -= mod;
    }
    return (int)ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int A = 1, B = 2, C = 3;
    System.out.println(maxsubsequence(A, B, C));
  }
}
 
// This code is contributed by Taranpreet

# python3 Code for the above approach:
def maxsubsequence(A, B, C):
 
    # As the answer may be very large,
    # Find it modulo 109 + 7
    mod = int(1e9 + 7)
 
    # Count possible subsequence by
    # A times"1" and B times"10"
    ans = (A * 1 * B) % mod + ((B * 1 * (B + 1)) // 2) % mod
    if (ans >= mod):
        ans -= mod
 
    # Count possible subsequence
    # By C times "0" and A & B time "1"
    ans += ((A + B) * 1 * C) % mod
    if (ans >= mod):
        ans -= mod
 
    return ans
 
# Driver code
if __name__ == "__main__":
 
    A, B, C = 1, 2, 3
    print(maxsubsequence(A, B, C))
 
# This code is contributed by rakeshsahni

// C# Code for the above approach:
using System;
class GFG{
 
  static int maxsubsequence(int A, int B, int C)
  {
 
    // As the answer may be very large,
    // Find it modulo 109 + 7
    long mod = (long)(1e9 + 7);
 
    // Count possible subsequence by
    // A times"1" and B times"10"
    long ans = (long)(A * B) % mod
      + ((B * (B + 1)) / 2) % mod;
    if (ans >= mod) {
      ans -= mod;
    }
 
    // Count possible subsequence
    // By C times "0" and A & B time  "1"
    ans += ((A + B) * C) % mod;
    if (ans >= mod) {
      ans -= mod;
    }
    return (int)ans;
  }
 
  // Driver code
  static public void Main (){
 
    int A = 1, B = 2, C = 3;
    Console.Write(maxsubsequence(A, B, C));
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
        // JavaScript code for the above approach
function maxsubsequence( A, B, C)
{
 
    // As the answer may be very large,
    // Find it modulo 109 + 7
    let mod = 1e9 + 7;
 
    // Count possible subsequence by
    // A times"1" and B times"10"
    let ans
        = (A * 1 * B) % mod
          + ((B * 1* (B + 1)) / 2) % mod;
    if (ans >= mod) {
        ans -= mod;
    }
 
    // Count possible subsequence
    // By C times "0" and A & B time  "1"
    ans += ((A + B) * 1 * C) % mod;
    if (ans >= mod) {
        ans -= mod;
    }
    return ans;
}
 
// Driver code
 
    let A = 1, B = 2, C = 3;
    document.write(maxsubsequence(A, B, C) + '<br>');
   
     // This code is contributed by Potta Lokesh
    </script>

14

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)