C++(g++ 7.5.0) 解法, 执行用时: 14ms, 内存消耗: 516K, 提交时间: 2023-07-17 22:09:44

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
const ll mod=1e9+7;
ll tran[35][35],f[35][35],temp[35][35];
void mul(ll c[][35],ll a[][35],ll b[][35])
{
    memset(temp,0,sizeof(temp));
    for(ll i=0;i<(1<<m);i++)
        for(ll j=0;j<(1<<m);j++)
            for(ll k=0;k<(1<<m);k++)
                temp[i][j]=(temp[i][j]+(ll)(a[i][k]*b[k][j]))%mod;
    memcpy(c,temp,sizeof(temp));
}
int main()
{
	ll ans=0;
	cin>>m>>n;
	//所有状态均合法 
	for(ll i=0;i<(1<<m);i++)
		for(ll j=0;j<(1<<m);j++)
			if((i&j)==0&&(i|j))  tran[i][j]=1;//状态转移矩阵，白色为1，黑色为0
	for(ll i=0;i<(1<<m);i++)  f[i][i]=1;
	ll k=n-1;
	while(k)
	{
		if(k&1)  mul(f,f,tran);
		k>>=1;
		mul(tran,tran,tran);
	}
	for(ll i=0;i<(1<<m);i++)
		for(ll j=0;j<(1<<m);j++)  ans=(ans+f[i][j])%mod;
	cout<<ans;
}

C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 504K, 提交时间: 2020-09-22 23:09:41

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,ans=0;
long long m,a[35][35],b[35][35],c[35][35];
void mul(long long d[][35],long long e[][35]){
	memset(c,0,sizeof(c));
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<(1<<n);j++){
			for(int k=0;k<(1<<n);k++){
				c[i][k]=(c[i][k]+d[i][j]*e[j][k])%mod;
			}
		}
	}
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<(1<<n);j++){
			d[i][j]=c[i][j];
		}
	} 
}
int main(){
	scanf("%d%lld",&n,&m);
	m--;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<(1<<n);j++){
			if((i|j)&&!(i&j)){
				b[i][j]=1;
			}
		}
	}
	for(int i=0;i<(1<<n);i++){
		a[i][i]=1;
	}
	for(;m;m>>=1,mul(b,b))if(m&1)mul(a,b);
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<(1<<n);j++)ans=(ans+a[i][j])%mod;
    printf("%d\n",ans);
} 

C++ 解法, 执行用时: 11ms, 内存消耗: 432K, 提交时间: 2022-03-11 16:31:54

#include<bits/stdc++.h>
using namespace std;
const int mo=1e9+7;
long long n, m, ans, f[35][35], a[35][35];
void mul(long long a[35][35], long long b[35][35]){
	long long c[35][35]={0};
	for(int i=0; i<=m; i++){
		for(int j=0; j<=m; j++){
			for(int k=0; k<=m; k++){
				c[i][j]+=a[i][k]*b[k][j]%mo;
			}
			c[i][j]%=mo;
		}
	}
	memcpy(b, c, sizeof(c));
}
int main(){
	scanf("%lld%lld", &m, &n);
	m=(1<<m)-1, n--;
	for(int i=0; i<=m; i++){
		f[i][0]=1;
		for(int j=0; j<=m; j++){
			if((i|j)==m && (i&j)!=m) a[i][j]=1;
		}
	} 
	while(n){
		if(n&1) mul(a, f);
		mul(a, a), n>>=1;
	}
	for(int i=0; i<=m; i++) ans+=f[i][0];
	printf("%lld", ans%mo);
	return 0;
}