【TC SRM 671 Div1 Level3】BearDestroys（对角线——轮廓线DP）

传送门

题解：

看问题感觉不太是组合计数能够处理的东西。

看数据范围应该猜得到是DP，显然直接状压是不得行的。

可以感觉出来是一个轮廓线DP。

比较简单的想法就是按照熊推树的顺序进行转移，压一下轮廓线上哪些格子还没有被占。

但是很显然这样复杂度是 O ( 2 W W H ) O(2^WWH) O(2WWH)的， W W W有30感觉很不行，而且可以感觉出来，这个题的轮廓线状态几乎是满的，不存在什么凭借常数过题的可能性。。。

按照轮廓线DP的套路，我们希望能够选择较短的一维进行状压，这样压出来轮廓线也会小一点。

但是由于这道题需要计数的过程本身是一个有序转移。直接按照常规做法一格一格DP转移会有后效性。考虑下面这张图：

黄色是轮廓线，1号是我们当前处理的格子，我们发现我们在考虑1色格子的状态的时候需要考虑上面那个2号能不能盖住它，于是又需要考虑4号能不能被3号盖住。。。真这样讨论下去就没完没了了。。。

但是我们把会影响后效性的拿出来，发现实际上就是一条反对角线，从右上到左下的依次影响。

所以我们状压对角线。具体的转移细节和思路可以直接看代码，我自己写的时候注释写得很详细了（主要是有半年没有写过轮廓线DP了，自己理思路用的）。

代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

using std::cerr;
using std::cout;

int mod;
inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);}
inline int dec(int a,int b){a-=b;return a+(a>>31&mod);}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;}
inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;}
inline void Mul(int &a,int b){a=mul(a,b);}

class BearDestroys{
	private:
		static cs int SIZE=1<<15|1;
		int f[2][SIZE],g[2][SIZE],*pf,*nf,*pg,*ng;//pre now
		// f ：该状态的推倒的树的计数
		// g : 到达该状态的方案数计数 
		//状态定义 : dp[state] DP到当前格子，轮廓线状态为state
		//轮廓线压当前格子上方所有格子和左列下方所有格子 
		// state : 1 自由，0 禁用
		inline int get(int s,int t){if(t<0)return 0;return s>>t&1;}
		inline int set(int s,int t,int p){if(t<0)return s;return (s>>t&1)==p?s:(s^(1<<t));}
		int u[55],d[55],n,m,S;
	public:
		BearDestroys(){pf=f[0],nf=f[1],pg=g[0],ng=g[1];}
		int sumUp(int M,int N,int Mod){
			n=N,m=M,mod=Mod,S=1<<(n+1);
			for(int re i=0;i<m;++i)u[i]=0;
			for(int re i=m;i<n+m-1;++i)u[i]=i-m+1;
			for(int re i=n+m-2;i>=n-1;--i)d[i]=n-1;
			for(int re i=0;i<n-1;++i)d[i]=i;
			ng[0]=1;nf[0]=0;
			//不允许更改确定了状态的格子 
			for(int re i=0;i<n+m-1;++i){//枚举对角线 
				//在转移一条新的对角线之前刷新状态,扣掉最后一维无用状态并状态平移 
				std::swap(ng,pg);std::swap(nf,pf);
				memset(ng,0,sizeof(int)*S);
				memset(nf,0,sizeof(int)*S);
				for(int re s=0;s<S;++s)if(pg[s]||pf[s]){
					//最后一个自由格子的方案需要算入贡献
					int t=get(s,n); 
					Inc(ng[set(s,n,0)<<1],pg[s]);
					Inc(nf[set(s,n,0)<<1],pf[s]);
					if(t){
						Inc(ng[set(s,n,0)<<1],pg[s]);
						Inc(nf[set(s,n,0)<<1],pf[s]);
					}
				}
				for(int re j=0;j<n;++j){
					std::swap(ng,pg),std::swap(nf,pf);
					memset(ng,0,sizeof(int)*S);
					memset(nf,0,sizeof(int)*S);
					for(int re s=0;s<S;++s)if(pf[s]||pg[s]){
						int f=pf[s],g=pg[s];
						if(j<u[i]||d[i]<j){
							Inc(nf[set(s,j,0)],f);
							Inc(ng[set(s,j,0)],g);
							continue;
						}
						int t1=get(s,j-1),t2=get(s,j),t3=get(s,j+1);//右上，正上，左侧
						if(!t2){
						//正上格子禁用 
							if(t3){
							//左侧格子可用 
								//左侧格子决策为右，禁用左侧格子和当前格子 
								{//禁用了当前格子，需要算上当前格子的决策*2 
									int t=set(s,j,0);t=set(t,j+1,0);
									Inc(nf[t],add(add(f,f),add(g,g)));
									Inc(ng[t],add(g,g));
								}
								//左侧格子决策为下，考虑是否为最后一行
								{
									//如果是最后一行，必须右转，转移和上面一样 
									if(j==n-1){
										int t=set(s,j,0);t=set(t,j+1,0);
										Inc(nf[t],add(add(f,f),add(g,g)));
										Inc(ng[t],add(g,g));
									}
									//否则，这个格子自由了
									else {
										int t=set(s,j,1);
										Inc(nf[t],f);
										Inc(ng[t],g);
									}
								}
							}else {
							//左侧格子禁用，这个格子自由了 
								int t=set(s,j,1);
								Inc(nf[t],f);
								Inc(ng[t],g);
							} 
						}
						else {
							//这时候一定是正上方格子来压住这个格子,该格子禁用，需要计算该格子的贡献 
							int t=set(s,j,0);Inc(f,f),Inc(g,g);
							if(!t1){
							//如果右上方的格子禁用，则正上方格子可以任意，需要*2 
								Inc(nf[t],add(add(f,f),add(g,g)));
								Inc(ng[t],add(g,g));
							}else {
							//否则正上方格子只能是向下。
								Inc(nf[t],add(f,g));
								Inc(ng[t],g);
							}
						} 
					}
				} 
			}
			int ans=0;
			Inc(ans,nf[0]);
			Inc(ans,mul(2,nf[1<<n-1]));
			Inc(ans,mul(2,nf[1<<n]));
			Inc(ans,mul(4,nf[3<<n-1])); 
			return ans;
		}
};

#ifdef zxyoi

BearDestroys Solver;

signed main(){
	freopen("bear.in","r",stdin);
	int n,m,mod;scanf("%d%d%d",&n,&m,&mod);
	std::cout<<Solver.sumUp(m,n,mod)<<"\n";
	return 0;
}
#endif