Número de subconjuntos con un valor AND dado

Dada una array arr de longitud N y un entero X , la tarea es encontrar el número de subconjuntos cuyo valor AND es X.
Ejemplos: 
 

Entrada: arr[] = {2, 3, 2} X = 2 
Salida: 6 
Todos los subconjuntos posibles y sus valores AND son: 
{2} = 2 
{3} = 3 
{2} = 2 
{2, 3} = 2 & 3 = 2 
{3, 2} = 3 & 2 = 2 
{2, 2} = 2 & 2 = 2 
{2, 3, 2} = 2 & 3 & 2 = 2
Entrada: arr[] = {0, 0, 0}, X = 0 
Salida: 7 
 

Enfoque: Un enfoque simple es resolver el problema generando todos los subconjuntos posibles y luego contando el número de subconjuntos con el valor AND dado. Sin embargo, para valores más pequeños de elementos de array, se puede resolver mediante programación dinámica . 
Veamos primero la relación de recurrencia. 
 

dp[i][curr_and] = dp[i + 1][curr_and] + dp[i + 1][curr_and & arr[i]] 
 

La relación de recurrencia anterior se puede definir como el número de subconjuntos de subarreglo arr[i…N-1] de tal manera que si se les aplica AND con curr_and se obtiene el valor AND requerido. 
La relación de recurrencia se justifica ya que solo hay caminos. O bien, tome el elemento actual y Y con curr_and o ignórelo y avance.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define maxN 20
#define maxM 64
 
// To store states of DP
int dp1[maxN][maxM];
bool v1[maxN][maxM];
 
// Function to return the required count
int findCnt(int* arr, int i, int curr, int n, int m)
{
    // Base case
    if (i == n) {
        return (curr == m);
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v1[i][curr])
        return dp1[i][curr];
 
    // Setting the state as solved
    v1[i][curr] = 1;
 
    // Recurrence relation
    dp1[i][curr]
        = findCnt(arr, i + 1, curr, n, m)
          + findCnt(arr, i + 1, (curr & arr[i]), n, m);
 
    return dp1[i][curr];
}
 
// Driver code
int main()
{
    int arr[] = { 0, 0, 0 };
    int n = sizeof(arr) / sizeof(int);
    int m = 0;
 
    cout << findCnt(arr, 0, ((1 << 6) - 1), n, m);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
static int maxN = 20;
static int maxM = 64;
 
// To store states of DP
static int [][]dp1 = new int[maxN][maxM];
static boolean [][]v1 = new boolean[maxN][maxM];
 
// Function to return the required count
static int findCnt(int []arr, int i,
                   int curr, int n, int m)
{
    // Base case
    if (i == n)
    {
        return (curr == m ? 1 : 0);
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v1[i][curr])
        return dp1[i][curr];
 
    // Setting the state as solved
    v1[i][curr] = true;
 
    // Recurrence relation
    dp1[i][curr] = findCnt(arr, i + 1, curr, n, m) +
                   findCnt(arr, i + 1, (curr & arr[i]), n, m);
 
    return dp1[i][curr];
}
 
// Driver code
public static void main(String []args)
{
    int arr[] = { 0, 0, 0 };
    int n = arr.length;
    int m = 0;
 
    System.out.println(findCnt(arr, 0, ((1 << 6) - 1), n, m));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
import numpy as np
 
maxN = 20
maxM = 64
 
# To store states of DP
dp1 = np.zeros((maxN, maxM));
v1 = np.zeros((maxN, maxM));
 
# Function to return the required count
def findCnt(arr, i, curr, n, m) :
 
    # Base case
    if (i == n) :
        return (curr == m);
 
    # If the state has been solved before
    # return the value of the state
    if (v1[i][curr]) :
        return dp1[i][curr];
 
    # Setting the state as solved
    v1[i][curr] = 1;
 
    # Recurrence relation
    dp1[i][curr] = findCnt(arr, i + 1, curr, n, m) + \
                   findCnt(arr, i + 1, (curr & arr[i]), n, m);
 
    return dp1[i][curr];
 
# Driver code
if __name__ == "__main__" :
     
    arr = [ 0, 0, 0 ];
    n = len(arr);
    m = 0;
 
    print(findCnt(arr, 0, ((1 << 6) - 1), n, m));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
static int maxN = 20;
static int maxM = 64;
 
// To store states of DP
static int [,]dp1 = new int[maxN, maxM];
static bool [,]v1 = new bool[maxN, maxM];
 
// Function to return the required count
static int findCnt(int []arr, int i,
                   int curr, int n, int m)
{
    // Base case
    if (i == n)
    {
        return (curr == m ? 1 : 0);
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v1[i, curr])
        return dp1[i, curr];
 
    // Setting the state as solved
    v1[i, curr] = true;
 
    // Recurrence relation
    dp1[i, curr] = findCnt(arr, i + 1, curr, n, m) +
                   findCnt(arr, i + 1, (curr & arr[i]), n, m);
 
    return dp1[i, curr];
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 0, 0, 0 };
    int n = arr.Length;
    int m = 0;
 
    Console.WriteLine(findCnt(arr, 0, ((1 << 6) - 1), n, m));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript implementation of the approach
 
var maxN = 20;
var maxM =  64;
 
// To store states of DP
var dp1 = Array.from(Array(maxN), ()=> Array(maxM));
var v1 = Array.from(Array(maxN), ()=> Array(maxM));
 
// Function to return the required count
function findCnt(arr, i, curr, n, m)
{
    // Base case
    if (i == n) {
        return (curr == m);
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v1[i][curr])
        return dp1[i][curr];
 
    // Setting the state as solved
    v1[i][curr] = 1;
 
    // Recurrence relation
    dp1[i][curr]
        = findCnt(arr, i + 1, curr, n, m)
          + findCnt(arr, i + 1, (curr & arr[i]), n, m);
 
    return dp1[i][curr];
}
 
// Driver code
var arr = [0, 0, 0];
var n = arr.length;
var m = 0;
document.write( findCnt(arr, 0, ((1 << 6) - 1), n, m));
 
</script>

7