CodePlus 2018 3 月赛白金元首与莫斯科插头DP

本文主要是介绍CodePlus 2018 3 月赛白金元首与莫斯科插头DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面：https://loj.ac/problem/6301

一眼就看出是一道插头DP题，只记录插头的有无。然而直接枚举每个格子当成障碍来算的话，时间复杂度是 $O(n^32^n)$ ，这里设 $m,n$ 同阶。这样做只有24分。

这道题空间开得很大，足足有1G。这启发我们可以记录所有状态。

于是想到，先假设只有那些已经确定的障碍格子，从左上角开始做一次插头DP，再从右下角做一次插头DP。记录所有状态的方案数。在把格子 $(i,j)$ 当成障碍算的时候，只需要把第一次插头DP在 $(i,j-1)$ 处合法的状态和第二次插头DP在 $(i,j+1)$ 处对应的状态找出来，相乘后累加到答案上即可。

发现“对应的状态”就是插头有无状态完全相同。总时间复杂度为 $O(nm2^m)$ ，实际合法的状态比这个还要少。

#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 266666
#define rg register
using namespace std;
const int mod=1e9+7;char *p1,*p2,buf[1<<20];
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){char s=GC;int sign=0,v=0;while((s!='-')&&(s>57||s<48))s=GC;if(s=='-')s=GC,sign=1;for(;s>47&&s<58;s=GC)v=v*10+s-48;if(sign)v=-v;return v;
}void Add(int &a,int b){a+=b;a-=a<mod?0:mod;
}int N,M,A[20][20],Ans[20][20],En;
int f[18][18][MAXN],g[18][18][MAXN];void PDP1(){int st,r,d,tmp;f[0][M][0]=1;for(rg int i=1;i<=N;i++){for(rg int j=0;j<=En;j++)Add(f[i][0][j<<1],f[i-1][M][j]);for(rg int j=1;j<=M;j++){for(rg int k=0;k<=En;k++){st=k;tmp=f[i][j-1][st];if(tmp==0)continue;r=st>>j-1&1;d=st>>j&1;if(!A[i][j]){if(!r&&!d)Add(f[i][j][st],tmp);}else if(!r&&!d){Add(f[i][j][st],tmp);if(A[i][j+1])Add(f[i][j][st^(1<<j)],tmp);if(A[i+1][j])Add(f[i][j][st^(1<<j-1)],tmp);}else if(r&&!d){Add(f[i][j][st^(1<<j-1)],tmp);}else if(!r&&d){Add(f[i][j][st^(1<<j)],tmp);}}}}
}void PDP2(){int st,r,d,tmp;g[N+1][1][0]=1;for(rg int i=N;i;i--){for(rg int j=0;j<=En;j++)Add(g[i][M+1][j>>1],g[i+1][1][j]);for(rg int j=M;j;j--){for(rg int k=0;k<=En;k++){st=k;tmp=g[i][j+1][st];if(tmp==0)continue;r=st>>j&1;d=st>>j-1&1;if(!A[i][j]){if(!r&&!d)Add(g[i][j][st],tmp);}else if(!r&&!d){Add(g[i][j][st],tmp);if(A[i-1][j])Add(g[i][j][st^(1<<j)],tmp);if(A[i][j-1])Add(g[i][j][st^(1<<j-1)],tmp);}else if(!r&&d){Add(g[i][j][st^(1<<j-1)],tmp);}else if(!d&&r){Add(g[i][j][st^(1<<j)],tmp);}}}}
}int main(){N=_R();M=_R();for(rg int i=1;i<=N;i++)for(rg int j=1;j<=M;j++)A[i][j]=_R(),A[i][j]^=1;En=(1<<M+1)-1;PDP1();PDP2();for(rg int i=1;i<=N;i++)for(rg int j=1;j<=M;j++)if(A[i][j]){int t=En^(1<<j)^(1<<j-1);for(rg int k=t;k;k=(k-1)&t)Add(Ans[i][j],(long long)f[i][j-1][k]*g[i][j+1][k]%mod);Add(Ans[i][j],(long long)f[i][j-1][0]*g[i][j+1][0]%mod);}for(rg int i=1;i<=N;i++,putchar('\n'))for(rg int j=1;j<=M;j++)printf("%d ",Ans[i][j]);
}