text: Sum of bitwise AND of all submatrices | C ++ program to find sum of Bit - wise AND of all submatrices ; Function to find prefix - count for each row from right to left ; Function to find the number of submatrices with all 1 s ; Array to store required prefix count of 1 s from right to left for boolean array ; Variable to store the final answer ; For each index of a column , determine the number of sub - matrices starting from that index and has all 1 s ; Stack to store elements and the count of the numbers they popped First part of pair is value of inserted element Second part is count of the number of elements pushed before with a greater value ; variable to store the number of submatrices with all 1 s ; Function to find the sum of Bitwise - AND of all submatrices ; matrix to store the status of ith bit of each element of matrix arr ; Driver Code
code: #include <iostream> NEW_LINE #include <stack> NEW_LINE using namespace std ; #define n  3 NEW_LINE void findPrefixCount ( int p_arr [ ] [ n ] , bool set_bit [ ] [ n ] ) { for ( int i = 0 ; i < n ; i ++ ) { for ( int j = n - 1 ; j >= 0 ; j -- ) { if ( ! set_bit [ i ] [ j ] ) continue ; if ( j != n - 1 ) p_arr [ i ] [ j ] += p_arr [ i ] [ j + 1 ] ; p_arr [ i ] [ j ] += ( int ) set_bit [ i ] [ j ] ; } } } int matrixAllOne ( bool set_bit [ ] [ n ] ) { int p_arr [ n ] [ n ] = { 0 } ; findPrefixCount ( p_arr , set_bit ) ; int ans = 0 ; for ( int j = 0 ; j < n ; j ++ ) { int i = n - 1 ; stack < pair < int , int > > q ; int to_sum = 0 ; while ( i >= 0 ) { int c = 0 ; while ( q . size ( ) != 0 and q . top ( ) . first > p_arr [ i ] [ j ] ) { to_sum -= ( q . top ( ) . second + 1 ) * ( q . top ( ) . first - p_arr [ i ] [ j ] ) ; c += q . top ( ) . second + 1 ; q . pop ( ) ; } to_sum += p_arr [ i ] [ j ] ; ans += to_sum ; q . push ( { p_arr [ i ] [ j ] , c } ) ; i -- ; } } return ans ; } int sumAndMatrix ( int arr [ ] [ n ] ) { int sum = 0 ; int mul = 1 ; for ( int i = 0 ; i < 30 ; i ++ ) { bool set_bit [ n ] [ n ] ; for ( int R = 0 ; R < n ; R ++ ) for ( int C = 0 ; C < n ; C ++ ) set_bit [ R ] [ C ] = ( ( arr [ R ] [ C ] & ( 1 << i ) ) != 0 ) ; sum += ( mul * matrixAllOne ( set_bit ) ) ; mul *= 2 ; } return sum ; } int main ( ) { int arr [ ] [ n ] = { { 9 , 7 , 4 } , { 8 , 9 , 2 } , { 11 , 11 , 5 } } ; cout << sumAndMatrix ( arr ) ; return 0 ; }