Number of subsets with a given AND value | Python3 implementation of the approach ; To store states of DP ; Function to return the required count ; Base case ; If the state has been solved before return the value of the state ; Setting the state as solved ; Recurrence relation ; Driver code
import numpy as np NEW_LINE maxN = 20 NEW_LINE maxM = 64 NEW_LINE dp1 = np . zeros ( ( maxN , maxM ) ) ; NEW_LINE v1 = np . zeros ( ( maxN , maxM ) ) ; NEW_LINE def findCnt ( arr , i , curr , n , m ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT return ( curr == m ) ; NEW_LINE DEDENT if ( v1 [ i ] [ curr ] ) : NEW_LINE INDENT return dp1 [ i ] [ curr ] ; NEW_LINE DEDENT v1 [ i ] [ curr ] = 1 ; NEW_LINE dp1 [ i ] [ curr ] = findCnt ( arr , i + 1 , curr , n , m ) + findCnt ( arr , i + 1 , ( curr & arr [ i ] ) , n , m ) ; NEW_LINE return dp1 [ i ] [ curr ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 0 , 0 , 0 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE m = 0 ; NEW_LINE print ( findCnt ( arr , 0 , ( ( 1 << 6 ) - 1 ) , n , m ) ) ; NEW_LINE DEDENT