记录编号	386770	评测结果	AAAWWWWWWW
题目名称	长方形骨牌覆盖	最终得分	30
用户昵称	农场主	是否通过	未通过
代码语言	C++	运行时间	2.976 s
提交时间	2017-03-25 08:05:00	内存使用	186.58 MiB

//1520
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int nmax=9765630;
ll f[2][nmax]={0};
int P[nmax]={0};
int R,N,M;
void PreDo(){
	scanf("%d%d%d",&R,&N,&M);
	P[0]=1;
	for(int i=1;i<=M;i++){
		P[i]=P[i-1]*R;
	}
	f[0][P[M]-1]=1;
}
void DFS(int n,int p,int s1,int 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*P[R],s2*P[R]);
}

void Cal(){
	if(N<M){
		swap(N,M);
	}
	for(int i=1;i<=N;i++){
		DFS(i&1,0,0,0);
		memset(f[(i&1)^1],0,sizeof(f[(i&1)^1]));
	}
	if(N%R&&M%R){
		printf("0\n");
		return ;
	}
	else{
		printf("%lld\n",f[N&1][P[M]-1]);
	}
}
int main(){
	freopen("examseven.in","r",stdin);
	freopen("examseven.out","w",stdout);
	PreDo();
	Cal();
	return 0;
}