求把NM的棋盘分割成若干个12的的长方形,有多少种方案。
例如当N=2,M=4时,共有5种方案。当N=2,M=3时,共有3种方案。
如下图所示:
输入格式
输入包含多组测试用例。
每组测试用例占一行,包含两个整数N和M。
当输入用例N=0,M=0时,表示输入终止,且该用例无需处理。
输出格式
每个测试用例输出一个结果,每个结果占一行。
数据范围
1≤N,M≤11
输入样例:
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出样例:
1
0
1
2
3
5
144
51205
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=12,M=1<<N;
ll n,m;
ll f[N][M];
bool st[M];
int main()
{
while(cin>>n>>m,n||m)
{
for(int i=0;i<1<<n; i++){
st[i]=true;
int cut=0; //当前连续0的个数
//0表示不放
for(int j=0;j<n;j++)
{
if(i>>j&1)
{ //如果遇到1,则连续性被断了,直接判断cnt是否是奇数
if(cut&1) //是奇数不成立
{
st[i]=false;
break;
}
cut=0;
}
else cut++; //如果是0,则继续寻找,并且0的数量加1
}
if(cut&1) st[i]=false;//判断末尾的情况
}
memset(f,0,sizeof(f));
f[0][0]=1;
for(ll i=1;i<=m;i++)
for(ll j=0;j<1<<n;j++) //枚举i列每一种状态
for(ll k=0;k<1<<n;k++) //枚举i列每一种状态 f[i][j]
if((j&k)==0&&st[j|k]) //f[i-1][k] 成功转到 f[i][j]
f[i][j]+=f[i-1][k];
// 棋盘一共有0~m-1列
// f[i][j]表示 从i-1列伸出来的是j的方案数;
// f[m][0]表示 从m-1列伸出来的是0的方案数;
// 也就是m列不放小方格,前m-1列已经完全摆放好并且不伸出来的状态
cout<<f[m][0]<<endl;
}
}