2015
04-13

# Puzzling Maze

Little A has a lovely toy dog , and she likes it so much . But bad B envy her happiness . So he robbed her little dog and put it in his partner C’s house. C’s house is like a big maze,so it’s so hard for A to find her toy . So she employed some robots to help her . These robots’ travel has some principles .

They’re listed as follows:

1.One robot can move horizontal and vertical, and it cannot stay at the start grid and not move.

2.Every robot’s path must be a circuit .

3.Every two robots’ travel path can not cross at any grid,and any grid in the maze must be stepped once and only once.

4.We don’t consider the direction those robots move.

5. You can use any numbers of robots, and there are infinitely many robots.

Only after traveling to every grid can A find her toy dog,she wonders how many ways to do this by using robots ?

The maze is like an "L" ,as show below. There are multiple test case. Each case contains 2 integers,n and m. We guarantee that m>=n,m<=10^9,1<=n<=7.

The maze is like an "L" ,as show below. There are multiple test case. Each case contains 2 integers,n and m. We guarantee that m>=n,m<=10^9,1<=n<=7.

2 2
2 3
2 4

Case 1: 1
Case 2: 1
Case 3: 4
HintAnswers to the sample input are shown below .



#include <stdio.h>
#include <string.h>
#define maxn 150
#define mod 1000000007
struct matrix{
int v[70][70];
void clear(){
memset(v,0,sizeof(v));
}
} a,b;
int st_num[maxn],stn;
int n,m;
int ans;
int f[10][10][maxn];
int q[2][maxn],qn[2];
if (p==n){
}
return;
}
if (c1 && c2){
}else
if (c1 || c2){
}else{
}
}
matrix mat_mul(matrix a,matrix b){
matrix c;
for (int i=0;i<stn;i++)
for (int j=0;j<stn;j++){
c.v[i][j]=0;
for (int k=0;k<stn;k++)
c.v[i][j]=(c.v[i][j]+(long long)a.v[i][k]*b.v[k][j])%mod;
}
return c;
}
matrix Mul(int p){
matrix ret,ta=a;
ret.clear();
for (int i=0;i<stn;i++) ret.v[i][i]=1;
while (p){
if ((p&1)>0) ret=mat_mul(ret,ta);
ta=mat_mul(ta,ta);
p>>=1;
}
return ret;
}
}
x=(x+v)%mod;
}
int cal(int st1,int st2,int c1,int c2){
int ret=0;
int now=0,next;
qn[0]=1;
q[0][0]=st1;
memset(f,0,sizeof(f));

for (int i=0;i<n;i++){
next=now^1;
qn[next]=0;
for (int p=0;p<qn[now];p++){
int st=q[now][p];
if (i==0 || getBit(st,n)==getBit(st2,i-1)){
if (i==0){
f[0][0][st<<1]=1;
q[next][qn[next]++]=st<<1;
}else{
int nst=st;
if (getBit(st2,i-1)) nst-=(1<<n);
q[next][qn[next]++]=nst<<1;
}
}
}
now=next;
// if (i==1){
// for (int c=0;c<qn[now];c++) printf("%d ",f[i][0][q[now][c]]);puts("");
// }

for (int j=0;j<n;j++){
next=now^1;
qn[next]=0;
for (int p=0;p<qn[now];p++){
int st=q[now][p],nst;
int c1=getBit(st,j),c2=getBit(st,j+1);
// if (i==1 && j==1) printf("!%d %d %d\n",st,c1,c2);
if (c1 && c2){
nst=st^(1<<j)^(1<<j+1);
if (f[i][j+1][nst]==0){
q[next][qn[next]++]=nst;
}
}else
if (c1 || c2){
nst=st;
// if (i==1 && j==1) printf("%d\n",nst);
if (f[i][j+1][nst]==0){

// if (i==1 && j==1) printf("%d\n",nst);
q[next][qn[next]++]=nst;
}

nst=st^(1<<j)^(1<<j+1);
// if (i==1 && j==1) printf("%d\n",nst);
if (f[i][j+1][nst]==0){
// if (i==1 && j==1) printf("%d\n",nst);
q[next][qn[next]++]=nst;
}
}else{
nst=st^(1<<j)^(1<<j+1);
if (f[i][j+1][nst]==0){
q[next][qn[next]++]=nst;
}
}
}
now=next;
}
}
for (int i=0;i<qn[now];i++){
int st=q[now][i];
if (getBit(st,n)==getBit(st2,n-1)){
int nst=st;
if (getBit(st,n)) nst-=(1<<n);
}
}
long long tmp=ret;
tmp*=c1;
tmp%=mod;
tmp*=c2;
tmp%=mod;
ret=tmp;
return ret;
}
int main(){
int cp=0;
while (scanf("%d%d",&n,&m)!=EOF){
printf("Case %d: ",++cp);
if (n%2){
puts("0");
continue;
}
stn=0;
memset(st_num,-1,sizeof(st_num));
for (int i=0;i<(1<<n);i++){
int k=0;
for (int j=0;j<n;j++)
if ((i&(1<<j))>0) k++;
if (k%2==0){
st_num[i]=stn++;
}
}
a.clear();
for (int i=0;i<(1<<n);i++)
if (st_num[i]>-1) dfs(0,i<<1,i);
b=Mul(m-n);

ans=0;
for (int i=0;i<(1<<n);i++)
for (int j=0;j<(1<<n);j++){
int si=st_num[i],sj=st_num[j];
if (b.v[0][si] && b.v[0][sj]) ans=(ans+cal(i,j,b.v[0][si],b.v[0][sj]))%mod;
}
printf("%d\n",ans);
}
return 0;
}

1. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

2. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

3. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

4. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

5. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

6. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

7. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

8. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

9. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

10. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

11. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

12. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

13. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

14. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

15. 基于尊老爱幼中国传统道德理念。不过这个事情了，小孩子既然已经坐下了，那么少妇完全就不属于弱势了，也就不必让座。毕竟孕妇和带小孩的乘客是弱势的原因是有个无法自理的孩子。

16. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

17. “可以发现,树将是满二叉树,”这句话不对吧，构造的树应该是“完全二叉树”，而非“满二叉树”。