就差一个点了,有没有大佬愿意瞟一眼看看怎么治疗MLE
查看原帖
就差一个点了,有没有大佬愿意瞟一眼看看怎么治疗MLE
180924
FLAT_LCH楼主2022/3/24 13:30
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

#define ll long long
#define mod 1000000007

using namespace std;

ll n,m,pos[20],rig,s;
ll f[20][20][(1<<18)+900]={};
ll g[20][20][(1<<18)+900]={};
ll ans[20][20]={};
bool map[20][20],st1,st2,st3;

inline ll rd()
{
	ll s=0;char x='x';
	while(x<'0'||x>'9')x=getchar();
	while(x>='0'&&x<='9'){s=s*10+(x^48);x=getchar();}
	return s;
}

inline void add(ll &x,ll y)
{
	x+=y;
	if(x>=mod)x-=mod;
}

int main()
{
	n=rd();m=rd();
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			map[i][j]=!rd();
			//cout<<map[i][j]<<' ';
		}
		//cout<<endl;
	}
	
	for(ll i=0;i<=m;i++)pos[i]=(1<<i);
	rig=(1<<m+1)-1;
	
	f[0][m][0]=1;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=0;j<=rig;j++)
			add(f[i][0][j<<1],f[i-1][m][j]);
		for(ll j=1;j<=m;j++)
		{
			for(ll k=0;k<=rig;k++)
			{
				s=f[i][j-1][k];
				st1=(k>>(j-1))&1;
				st2=(k>>j)&1;
				
				if((st1&&st2)||s==0)continue;
				
				if(map[i][j])
				{
					if(st1==0&&st2==0)
					{
						add(f[i][j][k],s);
						if(map[i+1][j])
							add(f[i][j][k+(1-st1)*pos[j-1]+(0-st2)*pos[j]],s);
						if(map[i][j+1])
							add(f[i][j][k+(0-st1)*pos[j-1]+(1-st2)*pos[j]],s);
					}
					else if(st1)
					{
						//if(map[i+1][j])
							add(f[i][j][k+(0-st1)*pos[j-1]+(0-st2)*pos[j]],s);
					}
					else if(st2)
					{
						//if(map[i][j+1])
							add(f[i][j][k+(0-st1)*pos[j-1]+(0-st2)*pos[j]],s);
					}
				}
				else
				{
					if(st1==0&&st2==0)
						add(f[i][j][k],s);
				}
			}
		}
	}
	
	g[n+1][1][0]=1;
	//cout<<rig<<endl;
	for(ll i=n;i>=1;i--)
	{
		for(ll j=0;j<=rig;j++)
			add(g[i][m+1][j>>1],g[i+1][1][j]);
		for(ll j=m;j>=1;j--)
		{
			for(ll k=0;k<=rig;k++)
			{
				s=g[i][j+1][k];
				//cout<<i<<' '<<j<<' '<<' '<<k<<' '<<s<<endl;
				st1=(k>>(j-1))&1;
				st2=(k>>j)&1;
				
				if((st1&&st2)||s==0)continue;
				
				if(map[i][j])
				{
					if(st1==0&&st2==0)
					{
						add(g[i][j][k],s);
						if(map[i-1][j])
							add(g[i][j][k+(0-st1)*pos[j-1]+(1-st2)*pos[j]],s);
						if(map[i][j-1])
							add(g[i][j][k+(1-st1)*pos[j-1]+(0-st2)*pos[j]],s);
					}
					else if(st1)
					{
						//if(map[i][j-1])
							add(g[i][j][k+(0-st1)*pos[j-1]+(0-st2)*pos[j]],s);
					}
					else if(st2)
					{
						//if(map[i-1][j])
							add(g[i][j][k+(0-st1)*pos[j-1]+(0-st2)*pos[j]],s);
					}
				}
				else
				{
					if(st1==0&&st2==0)
						add(g[i][j][k],s);
				}
			}
		}
	}
	
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			if(map[i][j]==0)
			{
				printf("0 ");
				continue;
			}
			for(ll k=0;k<=rig;k++)
			{
				st1=(k>>(j-1))&1;
				st2=(k>>j)&1;
				if(st1==0&&st2==0)
				{
					add(ans[i][j],g[i][j+1][k]*f[i][j-1][k]%mod);
				}
			}
			printf("%lld ",ans[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}
2022/3/24 13:30
加载中...