【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