State compression DP Mondrian's dream

Topic link ：

291. Mondrian's dream - AcWing Question bank https://www.acwing.com/problem/content/description/293/

f[i][j] Express ： front i - 1 The columns are in place , And from the i - 1 Lie Xiangdi i The status of leyanshen is j

The core ：
The number of small square schemes placed Equivalent to The number of small square schemes placed horizontally

How to judge whether the current scheme is legal ？
Traverse each column ,i The number of schemes in the column is only equal to i-1 List related

1.   j&k==0, i-2 The column extends to i-1 The little squares of and i-1 Small square for column placement No repetition .
2.    Each column , All continuous empty squares must be even

#include<bits/stdc++.h>
using namespace std;

const int N = 10, M = 1 << N;
//M  Each bit of binary stores a bit state 

int st[M];
// Store the legal placement status on each column 

long long f[N][M];
//f[i][j] Express ： front  i-1  The columns are in place , And from the i-1  Lie Xiangdi  i The status of leyanshen is j

// &  Only two are  1  Only then  1
// |  There is one  1  Namely  1
// ^  The difference between the two numbers is  1

int main()
{
    int n, m;   cin >> n >> m;
    for(int i = 0; i < 1 << n; i++)// Enumerate which of the placeholder states of each column is legal 
    {                              //i * 2 Of  n Power ,i Of  2 Hexadecimal shift left  n position , 
                                   // altogether  n  Column , There are two cases in each grid , by  0（ Don't put ）, by  1（ discharge ）
        int cnt = 0;
        //  Record in a column  0  The number of 
        st[i] = true;
        for(int j = 0; j < n; j++)// Enumerate every bit from low to high 
            if(i >> j & 1)// If the bit is  1
            {
                if(cnt & 1)//cnt  It is true when it is an odd number 
                //cnt & 1  It's true , It means continuous  0  It's odd 
                st[i] = false;
                cnt = 0;
            }
            else    cnt ++;
            //  This bit is  0, 0  The number of ++
        if(cnt & 1) st[i] = false;
        // At the end   Judge the front  0  The number of 
    }
    
    f[0][0] = 1;
    // non-existent  -1 Column , So the first  0 Xing di  0 Column   There will be no extended horizontal small squares 
    for(int i = 1; i <= m; i++)//  Traverse each column 
    {
        for(int j = 0; j < 1 << n; j++)// Traverse  i List each state 
        {
            for(int k = 0; k < 1 << n; k++)// Traverse  i - 1 List each state 
            if((j & k) == 0 && (st[j | k]))
            //  Two transfer conditions ： 
            //i  Column sum  i - 1 List the same row and poke it out at the same time  ; 
            // The status of this column  j  And the State mentioned above  k  Seek or ,
            // Get whether the above column is in odd empty row status , Odd blank lines do not transfer .
            //st[j | k] == 1  Express   stay  i  Column status  j, i - 1  Column status  k  Is legal .
                f[i][j] += f[i - 1][k];
                // State shift 
        }
    }
    cout<< f[m][0];
    // front  m - 1 The column has been placed ,  And there's no m - 1 Line up  m  Column extension 
    return 0;
}