题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4332
题目意思：
用1*1*2的长方体构造一个中间为空的底面3*3的立体烟囱。
解题思路：
实际上就是poj上这道题的升华版。推荐先做那道题。
只不过本题的每一层相当于poj上那题的每一行，此题层数很多，所以很直白的想到用矩阵快速幂加速。
这类型的矩阵乘法做的比较少。
用二维矩阵表示两层之间的转移关系，第一维表示上一层的状态，第二维表示下一层的状态，作为基矩阵。每次乘以它就相当于加了一层。状态图和矩阵转移如下，虽然很丑，但还看的清。
0表示当前层不放，那么它下面的一层肯定要为1（并且还是竖着的1），
1表示当前层放，可以是平着，也可以是竖着。（最后在统计最后一层平放的情况，最后一层竖着放肯定不行，超过了）
因为要多次调用基矩阵的偶次方，故预处理给保存起来。
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std; /*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/ #define Maxn 300
#define M 1000000007 struct Mar
{
int r,c;
ll sa[Maxn][Maxn]; void init(int a,int b) //矩阵的初始化
{
r=a,c=b;
memset(sa,0,sizeof(sa));
} };
Mar mar[35]; //mar[][i][j] 表示从当前层i状态转到下一层的j状态的种数
//这种矩阵构造还是第一次见
ll ans[Maxn],tmp[Maxn];
int m; Mar operator *(const Mar &a,const Mar &b)
{
Mar cc;
cc.init(a.r,b.c); for(int k=0;k<=a.c;k++) //注意要从0开始，因为0也是一种状态，纠结了好半天
{
for(int i=0;i<=a.r;i++)
{
if(a.sa[i][k]==0) //矩阵优化加速，把a矩阵的列或b矩阵的行 作为第一个循环
continue;
for(int j=0;j<=b.c;j++)
{
if(b.sa[k][j]==0)
continue;
cc.sa[i][j]=(cc.sa[i][j]+a.sa[i][k]*b.sa[k][j])%M;
}
}
}
return cc;
}
bool can[Maxn]; bool ok(int st) //是否有含有偶数个1 是的话可以横着放
{
if(st==0)
return true;
int i=0;
while((st&(1<<i))&&(i<8)) //找到第一个不是1的位置
i++;
if(i>=8)
return true;
for(int j=i+1;j<=i+8;j++) //循环起来，最多只需找8位
{
if(st&(1<<(j%8))) //两个两个一找
{
if(st&(1<<((j+1)%8)))
j++;
else
return false;
}
}
return true;
}
void iscan()
{
memset(can,false,sizeof(can));
for(int i=0;i<m;i++)
if(ok(i)) //有偶数个连续的1
can[i]=true;
return ;
} void Initba()
{//mar[0]应该是base mar[1]为base^2 mar[2]为base^4
mar[0].init(m-1,m-1);
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
{
if((i|j)==m-1&&can[i&j])
mar[0].sa[i][j]=1;
}
mar[0].sa[m-1][m-1]=2;// 此时下面一层可以有两种放法，题目中的第一个样例
for(int i=1;i<32;i++) //先预处理起来，因为每次都要计算矩阵的话，很慢
mar[i]=mar[i-1]*mar[i-1];
}
void mul(int x)
{
memset(tmp,0,sizeof(tmp));
for(int i=0;i<m;i++) //奇数的话 乘以一个
{
for(int j=0;j<m;j++)
tmp[i]=(ans[j]*mar[x].sa[j][i]+tmp[i])%M;
}
for(int i=0;i<m;i++)
ans[i]=tmp[i];
} void quick(int n)
{
memset(ans,0,sizeof(ans));
ans[m-1]=1; //表示第一层必须全为1才可能在上面放，1是一个标识，表示之前的0层的数量
n--; //第一层已经放好了
for(int i=0;n&&i<32;i++)
if(n&(1<<i))
mul(i);
} int main()
{
m=1<<8;
// printf("%d\n",m);
iscan();
Initba();
int n,t;
scanf("%d",&t);
for(int ca=1;ca<=t;ca++)
{
scanf("%d",&n);
quick(n);
ll sum=0;
for(int i=0;i<m;i++)
if(can[i]) //最后一层可以平铺
{
sum=(sum+ans[i])%M;
if(i==m-1) //最后一层有两种平铺法
sum=(sum+ans[i])%M;
}
printf("Case %d: %I64d\n",ca,sum);
}
return 0;
}