【JZOJ 5990】Bear

Description

link

Analysis

樸素dp是逐行逐格轉移

注意到 n n n較小， m m m較大

一個顯然的想法是看看能否逐列逐格轉移，很可惜不行，因為考慮棋盤覆寫順序，行的限制優先于列

但是考慮行和列覆寫情況什麼時候會沖突，隻可能是形如2*2的小正方形裡，左下和右上對右下格覆寫的時候沖突了，并且我們知道右上的優先級更高

這啟示了我們可以以左往右逐個斜線，每條斜線再從上到下的順序來dp，記錄輪廓線狀态即可

O ( 2 n + 1 n m ) O(2^{n+1}nm) O(2n+1nm)

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<assert.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,b,a) for(int i=(b);i>=(a);--i)
#define mset(a,x) memset(a,x,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(b))
using namespace std;
typedef long long ll;
int n,m;ll mo;
void inc(ll &x,ll y){x=(x+y)%mo;}
ll _2[33],f[50][15][8200],g[50][15][8200];
int main()
{
	freopen("bear.in","r",stdin);
	//freopen("bear.out","w",stdout);
	_2[0]=1;fo(i,1,30) _2[i]=_2[i-1]<<1;
	scanf("%d %d %lld",&n,&m,&mo);
	g[1][1][0]=1;
	fo(i,1,m+n-1)
		fo(j,1,n)
		{
			int y=i-j+1;
			if(y<1 || y>m)
			{
				fo(s,0,_2[n+1]-1)
					if(j==n)
					{
						inc(f[i+1][1][s>>1],f[i][n][s]);
						inc(g[i+1][1][s>>1],g[i][n][s]);
					}
					else
					{
						inc(f[i][j+1][s>>1],f[i][j][s]);
						inc(g[i][j+1][s>>1],g[i][j][s]);
					}
				continue;
			}
			fo(s,0,_2[n+1]-1) if(f[i][j][s] || g[i][j][s])
			{
				if(j==n)
				{
					if(s & _2[0])
					{
						inc(f[i+1][1][s>>1],2*f[i][n][s]);
						inc(g[i+1][1][s>>1],2*g[i][n][s]);
					}
					else
					{
						//E & S
						ll &nf = (s & _2[n]) ? f[i+1][1][s>>1] : f[i+1][1][(s>>1)|_2[n-1]];
						ll &ng = (s & _2[n]) ? g[i+1][1][s>>1] : g[i+1][1][(s>>1)|_2[n-1]];
						inc(nf,2*f[i][n][s]);
						if(!(s & _2[n])) inc(nf,2*g[i][n][s]);
						inc(ng,2*g[i][n][s]);
					}
					continue;
				}
				if(s & _2[0])
				{
					inc(f[i][j+1][s>>1],2*f[i][j][s]);
					inc(g[i][j+1][s>>1],2*g[i][j][s]);
				}
				else
				{
					//E
					ll &nef = ((s & _2[n]) || (y==m)) ? f[i][j+1][(s>>1)|_2[n]] : f[i][j+1][(s>>1)|_2[n-1]];
					ll &neg = ((s & _2[n]) || (y==m)) ? g[i][j+1][(s>>1)|_2[n]] : g[i][j+1][(s>>1)|_2[n-1]];
					inc(nef,f[i][j][s]+g[i][j][s]);
					inc(neg,g[i][j][s]);
					//S
					ll &nsf = f[i][j+1][(s>>1)|_2[n]];
					ll &nsg = g[i][j+1][(s>>1)|_2[n]];
					inc(nsf,f[i][j][s]+g[i][j][s]);
					inc(nsg,g[i][j][s]);
				}
			}
		}
	ll ans=0;
	fo(s,0,_2[n+1]-1)
		inc(ans,f[m+n-1][n][s]);
	printf("%lld\n",ans*2%mo);//ERR: forget to %mo at last
	return 0;
}