[acwing 327. corn field] shaped pressure DP

Topic link

The question ：

Farmer John's land consists of M×N It's made up of little squares , Now he's going to plant corn in the land .

Very regret , Part of the land is sterile , Unable to plant .

and , Adjacent land cannot grow corn at the same time , In other words, there will be no common edge between all squares planting corn .

Now given the size of the land , Please find out how many planting methods there are .

It's a way to plant nothing on the land .

Input format
The first 1 Line contains two integers M and N.

The first 2…M+1 That's ok ： Each row contains N It's an integer 0 or 1, Used to describe the condition of the whole land ,1 Indicates that the land is fertile ,0 Indicates that the land is sterile .

Output format
Output the total planting method to 108 The value after taking the mold .

analysis ：

Enumerate the planting status of each row , This state is to choose one or more from the state given in the title , Then judge whether each state is legal, and then enumerate the transferred States , Now let's look at the code ：

#include<bits/stdc++.h>
using namespace std;
const int N = 13,mod = 1e8;
typedef long long LL;
LL f[N][1<<N];
int g[N];
vector<int> hefa;
int main(){
    
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
    
		int x;
		for(int j=1;j<=m;j++){
    
			cin>>x;
			g[i] = g[i]*2 + x;
		}
	}
	for(int i=0;i<(1<<m);i++){
    
		if((i&(i>>1))==0) hefa.push_back(i);
	}
	f[0][0] = 1;
	LL ans = 0;
	for(int i=1;i<=n;i++){
    
		for(auto j : hefa){
    
			if((g[i]|j) == g[i]){
    
				for(auto x : hefa){
    
					if((j&x)==0)
						f[i][j] = (f[i][j]+f[i-1][x])%mod;
				}
			}
			if(i == n) ans = (ans + f[i][j]) % mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}