【轮廓线DP】SRM671 D1L3 BearDestroys
题意：
在一个N*M的矩阵中，每个位置有一棵树，以及一个字符’S’或’E’
一颗树被推倒后，会占据其周围的一个格子（向右推占右边的，向下推占下边的）
但是如果那个方向有被推倒的树，则不能推倒这棵树。如果这个格子被其他格子的树占到了，也不能推倒。
现在有一头熊，从第一行开始，从左往右依次推倒每一个格子中的树。
首先，它会尽可能使用这个格子中字符的方向，如果不能再使用另一个方向。
现在求对于所有的方案，被推倒的树的个数之和。
分析：
倾斜的轮廓线DP题。。。
DP[x][y][mask]表示，在(x,y)位置，且轮廓线上被选择情况为mask时的方案数（另外还要用一个数组存答案）
为了方便起见，我们不考虑轮廓线上没有被覆盖的格子中的符号。
以一条反对角线为DP的轮廓线
处理红色格子时，轮廓线应有的形状。
首先，如果B格未被占据，那么必然会有一棵树在B和红色格上。
此时如果C被占据，那么B用任意一个字符均可，若C未被占据，那么B只能用‘S’
如果A格未被占据，那么可以选择在红色格和B上放一颗树。若此时A在最后一行，那么A用任意一个字符都行，否则只能用‘E’
另外，被覆盖的格子（红色格）用任意一种颜色均可。
最后，在每一个对角线末尾时：
此时X如果为空，那么填任意一个字符均可。
最后，为了简单期间，我们可以把矩阵换成这个样子：
其中红色部分是原图。
然后，就可以过了。。。
（上面最后一个步卡了我半个多小时。。。）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 50
#define MAXS 65536
using namespace std;
typedef long long ll;
ll dp[2][MAXS],num[2][MAXS];
int n,m,now;
ll mod;
int main(){
SF("%d%d%lld",&n,&m,&mod);
dp[now][(1<<(m+1))-1-1]=1;
for(int i=0;i<n+m;i++){
for(int j=1;j<m;j++){
now^=1;
memset(dp[now],0,sizeof dp[now]);
memset(num[now],0,sizeof num[now]);
for(int mask=0;mask<(1<<(m+1));mask++){
int tag1=(mask>>(j-1))&1;
int tag2=(mask>>j)&1;
int tag3=(mask>>(j+1))&1;
if(i-j<0||i-j>=n){
(dp[now][mask|(1<<j)]+=dp[now^1][mask])%=mod;
(num[now][mask|(1<<j)]+=num[now^1][mask])%=mod;
}
else if(tag2==0){
(dp[now][mask|(1<<j)]+=2*(1+tag1)*dp[now^1][mask])%=mod;
(num[now][mask|(1<<j)]+=2*(1+tag1)*num[now^1][mask]+2*(1+tag1)*dp[now^1][mask])%=mod;
}
else{
if(tag3==0){
(dp[now][mask|(1<<j)|(1<<(j+1))]+=2*(1+(j==m-1))*dp[now^1][mask])%=mod;
(num[now][mask|(1<<j)|(1<<(j+1))]+=2*(1+(j==m-1))*num[now^1][mask]+2*(1+(j==m-1))*dp[now^1][mask])%=mod;
}
if(tag3!=0||j!=m-1){
(dp[now][mask&(~(1<<j))]+=dp[now^1][mask])%=mod;
(num[now][mask&(~(1<<j))]+=num[now^1][mask])%=mod;
}
}
// PF("[%d %d %d %lld %lld]\n",i-j,j,mask,dp[now^1][mask],num[now^1][mask]);
}
}
memset(dp[now^1],0,sizeof dp[now]);
memset(num[now^1],0,sizeof num[now]);
for(int mask=0;mask<(1<<(m+1));mask++){
// PF("[%d %d %lld %lld]\n",i,mask,dp[now][mask],num[now][mask]);
int tag=(mask>>m)&1;
int mask1=(mask<<1)&((1<<(m+1))-1);
if(i+1-1>=n-1){
(dp[now^1][mask1|1]+=(1+(tag==0))*dp[now][mask])%=mod;
(num[now^1][mask1|1]+=(1+(tag==0))*num[now][mask])%=mod;
}
else{
if((mask1&2)==0){
(dp[now^1][mask1|3]+=2*(1+(m==1))*(1+(tag==0))*dp[now][mask])%=mod;
(num[now^1][mask1|3]+=2*(1+(m==1))*(1+(tag==0))*num[now][mask]+2*(1+(m==1))*(1+(tag==0))*dp[now][mask])%=mod;
}
if(m==1&&i%2==0)
continue;
(dp[now^1][mask1]+=(1+(tag==0))*dp[now][mask])%=mod;
(num[now^1][mask1]+=(1+(tag==0))*num[now][mask])%=mod;
}
}
now^=1;
}
int ans=(num[now][(1<<(m+1))-1])%mod;
int res=(dp[now][(1<<(m+1))-1])%mod;
PF("%d",ans);
}