Lattice coloring - matrix fast power optimized shape pressure DP

Topic link

Normal embossing , But it's easy to see that the data is outrageous , This is bound to fail , It needs to be optimized

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
const int N = 6 ,M = 1<<5,mod=1e9+7;
int n,m;
int f[110][M];
signed main()
{
    
    cin>>n>>m;
    
    for(int i=0;i<1<<n;i++)f[1][i]=1;
    // 0  It's black  1  yes   white 
    for(int i=2;i<=m;i++)
    {
    
        for(int j=0;j<1<<n;j++)
        {
    
            for(int k=0;k<1<<n;k++)
            {
    
                if(j&k)continue;
                if((j|k)==0)continue;
                f[i][j]=(f[i][j]+f[i-1][k])%mod;
            }
        }
    }
    int res=0;
    for(int i=0;i<1<<n;i++)res+=f[m][i];
    cout<<res<<endl;
       
    
}

Fast power optimization method of matrix

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
const int N = 1<<5,mod=1e9+7;
int n,m;
int a[N][N],b[N][N];
void mul(int a[][N],int b[][N])
{
    
    int tmp[N][N]={
    0};
    for(int i=0;i<1<<n;i++)
        for(int j=0;j<1<<n;j++)
            for(int k=0;k<1<<n;k++)
                tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;
    for(int i=0;i<1<<n;i++)
        for(int j=0;j<1<<n;j++)
            a[i][j]=tmp[i][j];
}
signed main()
{
    
    cin>>n>>m;
    // The initial state 
    for(int i=0;i<1<<n;i++)a[i][i]=1;
    // 0  black 
    // 1  white 
    for(int i=0;i<1<<n;i++)
    {
    
        for(int j=0;j<1<<n;j++)
        {
    
            if(i&j)continue;
            if((i|j)==0)continue;
            b[i][j]=1;
        }
    }
    m--;
    while(m)
    {
    
        if(m&1)mul(a,b);
        mul(b,b);
        m>>=1;
    }
    int res=0;
    for(int i=0;i<1<<n;i++)
        for(int j=0;j<1<<n;j++)
            res=(res+a[i][j])%mod;
    cout<<res<<'\n';
}