木块砌墙

木块砌墙

用如下3种木块砌墙。

木块如上，不能翻转，墙如下图:

问有多少种方法。n<=1024 k<=4，答案对1000000007取余。

分析：

首先，因为木块的宽度都是1，我们可以想成2维的问题。也就是说三种木板的规格分别为1* 1, 1 * 2, 2 * 1。

看到这个问题最直接的想法就是暴力搜索。对每个空格尝试放置哪种木板。但是看看数据规模就知道，这种思路是不可行的。因为有一条边范围长度高达2¹⁰²⁴，普通的电脑，2³⁰左右就到极限了。于是我们猜测别的方法。

为了方便，我们把墙看做有2ⁿ行，k列的矩形。这是因为虽然矩形木块不能翻转，但是我们同时拥有1*2和2*1的两种木块。

假设我们从上到下，从左到右考虑每个1*1的格子是如何被覆盖的。显然，我们每个格子都要被覆盖住。木块的特点决定了我们覆盖一个格子最多只会影响到下一行的格子。这就可以让我们暂时只考虑两行。假设现我们已经完全覆盖了前(i– 1)行。那么由于覆盖前(i-1)行导致第i行也不“完整”了。如下图：我们用x表示已经覆盖的格子，o表示没覆盖的格子。为了方便，我们使用9列。

xxxxxxxxx

ooxooxoxo

我们考虑第i行的状态，假设如上图。第1列我们可以用1*1的覆盖掉，也可以用1*2的覆盖前两列。第3，4列的覆盖方式和第12列是同样地情况。第7列需要覆盖也有两种方式，即用1*1的覆盖或者用2*1的覆盖，但是这样会导致第（i+1)行第7列也被覆盖。第9列和第7列的情况是一样的。这样把第i行覆盖满了之后，我们再根据第(i+1)行被影响的状态对下一行进行覆盖。

那么每行有多少种状态呢？显然有2^k，由于k很小，我们只有大约16种状态。如果我们对于这些状态之间的转换制作一个矩阵，矩阵的第i行第j列的数表示的是我们第m行是状态i，我们把它完整覆盖掉，并且使得第(m + 1)行变成状态j的可能的方法数，这个矩阵我们可以暴力搜索出来，搜索的方式就是枚举第m行的状态，然后尝试放木板，用所有的方法把第m行覆盖掉之后，下一行的状态。这里，其实我们可以认为只有两行，并且第一行是2^k种状态的一种，第二行起初是空白的，求使得第一行完全覆盖掉，第二行的状态有多少种类型以及每种出现多少次。

这个矩阵作用很大，其实我们覆盖的过程可以认为是这样：第一行是空的，我们看看把它覆盖了，第2行是什么样子的。根据第二行的状态，我们把它覆盖掉，看看第3行是什么样子的。

如果我们知道第i行的状态为s,怎么考虑第i行完全覆盖后，第(i+1)行的状态？那只要看那个矩阵的状态s对应的行就可以了。我们可以考虑一下，把两个这样的方阵相乘得到得结果是什么。这个方阵的第i行第j个元素是这样得到的，是第i行第k个元素与第k行第j个元素的对k的叠加。它的意义是上一行是第m行是状态i，把第m行和第(m+ 1)行同时覆盖住，第(m+2)行的状态是j的方法数。这是因为中间第(m+1)行的所有状态k，我们已经完全遍历了。

于是我们发现，每做一次方阵的乘法，我们相当于把状态推动了一行。那么我们要坐多少次方阵乘法呢？就是题目中墙的长度2ⁿ,这个数太大了。但是事实上，我们可以不断地平方n次。也就是说我们可以算出A²,A⁴, A⁸, A¹⁶……方法就是不断用结果和自己相乘，这样乘n次就可以了。

因此，我们最关键的问题就是建立矩阵A。我们可以这样表示一行的状态，从左到右分别叫做第0列，第1列……覆盖了我们认为是1，没覆盖我们认为是0，这样一行的状态可以表示维一个整数。某一列的状态我们可以用为运算来表示。例如，状态x第i列是否被覆盖，我们只需要判断x & (1 << i) 是否非0即可，或者判断(x >> i) & 1， 用右移位的目的是防止溢出，但是本题不需要考虑溢出，因为k很小。 接下来的任务就是递归尝试放置方案了。

最终结果，我们最初的行是空得，要求最后一行之后也不能被覆盖，所以最终结果是矩阵的第[0][0]位置的元素。另外，本题在乘法过程中会超出32位int的表示范围，需要临时用C/C++的long long，或者java的long。

#ifdefWIN32
#definell__int64
#else
#definelllonglong
#endif

//1covered0uncovered

voidcal(inta[6][32][32],intn,intcol,intlaststate,intnowstate){
if(col>=n){
++a[n][laststate][nowstate];
return;
}
//不填或者用1*1的填
cal(a,n,col+1,laststate,nowstate);
if(((laststate>>col)&1)==0){
cal(a,n,col+1,laststate,nowstate|(1<<col));
if((col+1<n)&&(((laststate>>(col+1))&1)==0)){
cal(a,n,col+2,laststate,nowstate);
}
}
}

inlineintmul(llx,lly){
returnx*y%1000000007;
}

voidmultiply(intn,inta[][32],intb[][32]){//b=a*a
inti,j,k;
for(i=0;i<n;++i){
for(j=0;j<n;++j){
for(k=b[i][j]=0;k<n;++k){
if((b[i][j]+=mul(a[i][k],a[k][j]))>=1000000007){
b[i][j]-=1000000007;
}
}
}
}
}

intcalculate(intn,intk){
inti,j;
inta[6][32][32],mat[2][32][32];
memset(a,0,sizeof(a));
for(i=1;i<=5;++i){
for(j=(1<<i)-1;j>=0;--j){
cal(a,i,0,j,0);
}
}
memcpy(mat[0],a[k],sizeof(mat[0]));
k=(1<<k);
for(i=0;n;--n){
multiply(k,mat[i],mat[i^1]);
i^=1;
}
returnmat[i][0][0];
}