记录编号	184329	评测结果	AAAAAAAAAA
题目名称	长方形骨牌覆盖	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.978 s
提交时间	2015-09-02 18:21:59	内存使用	166.25 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
LL powr[20]={0};
LL f[2][10000000]={0};//r进制状态压缩
int N,M,r;
void DFS(int n,int p,int s1,int s2)//s1是当前行的状态，s2是上一行的
{
	if(p>M) return;
	if(p==M)
	{
		f[n][s1]+=f[n^1][s2];
		return;
	}
	for(int i=0;i<r-1;i++) DFS(n,p+1,s1*r+i,s2*r+(i+1)%r);
	DFS(n,p+1,s1*r+r-1,s2*r);
	DFS(n,p+r,s1*powr[r]+powr[r]-1,s2*powr[r]+powr[r]-1);
}
int main()
{
	freopen("examseven.in","r",stdin);
	freopen("examseven.out","w",stdout);
	scanf("%d%d%d",&r,&N,&M);
	if(M%r&&N%r)
	{
		printf("0\n");
		return 0;
	}
	powr[0]=1;
	for(int i=1;i<=M;i++) powr[i]=powr[i-1]*r;
	f[0][powr[M]-1]=1;
	for(int i=1;i<=N;i++){
		DFS(i&1,0,0,0);
		memset(f[(i&1)^1],0,sizeof(f[0]));
	}
	printf("%lld\n",f[N&1][powr[M]-1]);
	return 0;
}