C++(g++ 7.5.0) 解法, 执行用时: 46ms, 内存消耗: 18836K, 提交时间: 2022-09-27 18:45:33
#include<cstdio>
#include<cstring>
#define ri register int
#define ll long long
#define mo 1000000007
#define maxn 262145
#define fo(i,x,y) for(ri i(x);i<=y;++i)
#define fd(i,x,y) for(ri i(x);i>=y;--i)
using namespace std;
int n,m,a[19][19],f[18][18][maxn],p[21],cnt[2],las,now,q[2][maxn],val[2][maxn],mat[maxn];
int g[maxn],ans[19][19];
inline void add(ri i,ri j,ri bit,ri num){
if(!f[i][j][bit])q[now][++cnt[now]]=bit;
f[i][j][bit]+=num;f[i][j][bit]%=mo;
}
inline void add2(ri bit,ri num){
if(!mat[bit]){
mat[bit]=++cnt[now];q[now][cnt[now]]=bit;val[now][cnt[now]]=num;
}
else val[now][mat[bit]]=(val[now][mat[bit]]+num)%mo;
}
int main(){
scanf("%d%d",&n,&m);
fo(i,1,n)
fo(j,1,m)scanf("%d",&a[i][j]);
fo(i,1,n)
fo(j,1,m)a[i][j]^=1;
p[0]=1;fo(i,1,m+1)p[i]=p[i-1]<<1;
q[now][++cnt[now]]=0;f[0][m][0]=1;
fo(i,1,n)
fo(j,1,m){
las=now;now^=1;cnt[now]=0;
ri prex,prey;
if(j>1)prex=i,prey=j-1;
else prex=i-1,prey=m;
if(j==1){
memcpy(g,f[prex][prey],sizeof(f[prex][prey]));
memset(f[prex][prey],0,sizeof(f[prex][prey]));
fo(k,1,cnt[las])f[prex][prey][(q[las][k]<<1)&(p[m+1]-1)]=g[q[las][k]];
fo(k,1,cnt[las])q[las][k]=(q[las][k]<<1)&(p[m+1]-1);
}
fo(k,1,cnt[las]){
ri bit=q[las][k],l1=(bit>>j-1)&1,l2=(bit>>j)&1,num=f[prex][prey][bit];
if(l1&&l2)continue;
else{
if(l1)add(i,j,bit-p[j-1],num);
else{
if(l2)add(i,j,bit-p[j],num);
else{
add(i,j,bit,num);if(a[i][j]&&a[i+1][j])add(i,j,bit+p[j-1],num);
if(a[i][j+1]&&a[i][j])add(i,j,bit+p[j],num);
}
}
}
}
//if(i==1&&j==m)
//fo(k,1,cnt[now])printf("%d %d %d %d\n",i,j,q[now][k],f[i][j][q[now][k]]);
}
cnt[now]=0;add2(0,1);
fd(i,n,1)
fd(j,m,1){
//printf("YES\n");
ri px,py;las=now;now^=1;cnt[now]=0;memset(mat,0,sizeof(mat));
if(j==m)fo(k,1,cnt[las])q[las][k]>>=1;
if(j>1)px=i,py=j-1;
else px=i-1,py=m;
//printf("fd%d %d %d %d %d\n",i,j,cnt[las],px,py);
fo(k,1,cnt[las]){
//printf("%d %d %d %d\n",i,j,q[las][k],val[las][k]);
ri bit=q[las][k],l1=(bit>>j-1)&1,l2=(bit>>j)&1,num=val[las][k];
if(!l1&&!l2){
ri res=1ll*f[px][py][bit]*num%mo;
//printf("bit %d n1 %d n2 %d %d\n",bit,f[px][py][bit],num,res);
ans[i][j]+=res;ans[i][j]%=mo;
}
if(l1&&l2)continue;
else{
if(l1)add2(bit-p[j-1],num);
else{
if(l2)add2(bit-p[j],num);
else{
add2(bit,num);if(a[i][j]&&a[i][j-1])add2(bit+p[j-1],num);
if(a[i][j]&&a[i-1][j])add2(bit+p[j],num);
}
}
}
}
}
fo(i,1,n)
fo(j,1,m)if(!a[i][j])ans[i][j]=0;
fo(i,1,n){
fo(j,1,m-1)printf("%d ",ans[i][j]);
printf("%d\n",ans[i][m]);
}
return 0;
}
C++ 解法, 执行用时: 56ms, 内存消耗: 24056K, 提交时间: 2022-06-30 16:19:45
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 20021225
#define ll long long
#define mdn 1000000007
using namespace std;
int f[18][18][1<<17],g[18][18][1<<17];
int bit[18],n,m,top;
int mp[18][18];
void add(int &x,int y){x=(x+y)%mdn;}
void work()
{
//int top=(1<<m)-1;
f[1][1][top]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x=i,y=j+1;
if(j==m) x=i+1,y=1;
if(x>n) continue;
for(int st=0;st<=top;st++)
if(f[i][j][st])
{
int tmp=f[i][j][st];
if((st&bit[j])==0&&mp[i][j]) continue;
if((st&bit[j])==0)
{
add(f[x][y][st|bit[j]],tmp);
continue;
}
if(mp[i][j]) add(f[x][y][st],tmp);
else
{
add(f[x][y][st],tmp);
add(f[x][y][st^bit[j]],tmp);
if(j>1&&(st&bit[j-1])==0) add(f[x][y][st|bit[j-1]],tmp);
}
}
}
g[n][m][top]=1;
for(int i=n;i;i--)
for(int j=m;j;j--)
{
int x=i,y=j-1;
if(j==1) x=i-1,y=m;
if(x<1) continue;
for(int st=0;st<=top;st++)
if(g[i][j][st])
{
int tmp=g[i][j][st];
if((st&bit[j])==0&&mp[i][j]) continue;
//printf("%d %d %d %d\n",i,j,st,g[i][j][st]);
if((st&bit[j])==0)
{
add(g[x][y][st|bit[j]],tmp);
continue;
}
if(mp[i][j]) add(g[x][y][st],tmp);
else
{
add(g[x][y][st],tmp);
add(g[x][y][st^bit[j]],tmp);
if(j<m&&(st&bit[j+1])==0) add(g[x][y][st|bit[j+1]],tmp);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
bit[1]=1;top=(1<<m)-1;
for(int i=2;i<=m;i++) bit[i]=bit[i-1]<<1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&mp[i][j]);
work();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j])
{
printf("0 ");
continue;
}
int ans=0;
for(int s=0;s<=top;s++)
{
if(s&bit[j])
add(ans,(ll)f[i][j][s]*g[i][j][s]%mdn);
//printf("%d %d %d %d\n",i,j,f[i][j][s],g[i][j][s]);
}
printf("%d ",ans);
}
printf("\n");
}
return 0;
}
