记录编号	581622	评测结果	AAAAAAAAAA
题目名称	走道铺砖问题	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.160 s
提交时间	2023-08-09 16:26:52	内存使用	199.14 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = (1<<12)+10,MOD = 10000;
int n,m;
class PHint{
public:
	int n;
	int s[20];
	PHint(){n = 1;memset(s,0,sizeof(s));}
	void operator = (int x){
		memset(s,0,sizeof(s));
		n = 1;
		s[0] = x;
	}
	void operator += (const PHint &b){
		n = max(n,b.n)+1;
		for(int i = 0;i < n;i++){
			s[i] += b.s[i];
			s[i+1] += s[i] / MOD;
			s[i] %= MOD;
		}
		while(n > 1 && s[n-1] == 0)n--;
	}
	void print(void){
		printf("%d",s[n-1]);
		for(int i = n-2;i >= 0;i--)printf("%04d",s[i]);
		printf("\n");
	}
	
};
PHint f[42][14][N];
void dfs(int u,int p,int s1,int s2){
	if(p > m)return;
	f[u][p][s1] += f[u-1][p][s2];
	dfs(u,p+1,s1<<1,(s2<<1)+1);
	dfs(u,p+1,(s1<<1)+1,s2<<1);
	dfs(u,p+2,(s1<<2)+3,(s2<<2)+3);
}
int main(){
	freopen("floor.in","r",stdin);
	freopen("floor.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(n < m)n ^= m,m ^= n,n^= m;
	for(int i = 1;i <= m;i++)f[0][i][(1<<i)-1] = 1;
	for(int i = 1;i <= n;i++)dfs(i,0,0,0);
	f[n][m][(1<<m)-1].print();
	
	return 0;
	
}