首页 > ACM题库 > HDU-杭电 > HDU 4332-Constructing Chimney-状态压缩-[解题报告]HOJ
2015
05-23

HDU 4332-Constructing Chimney-状态压缩-[解题报告]HOJ

Constructing Chimney

问题描述 :

Now we are planning to construct a big chimney. The chimney’s section is a 3*3 square and the center of it will have nothing like the picture below. Now we only have a lot of bricks whose size if 1*1*2, and we want to build a chimney whose height is N, so can help us to calculate how many ways we can build the chimney? The answer may be very large, so you can just tell the answer’s remainder divided by 1000000007.
Image Recognition

输入:

The first line of the input contains an integer T (1<=T<=10) which means the number of test cases.
For each test cases, there is only one line with an integer N (1<=N<=10^9) which means the height of the chimney we want to build.

输出:

The first line of the input contains an integer T (1<=T<=10) which means the number of test cases.
For each test cases, there is only one line with an integer N (1<=N<=10^9) which means the height of the chimney we want to build.

样例输入:

2
1
2

样例输出:

Case 1: 2
Case 2: 49

题意:现在有无数的1*1*2的砖头,要垒成一个长度为N的烟囱。砖头可以竖起来,可以平着放,问题是当四块砖都平f放时,题目认为可以有两种情况。

做法:用0代表空,1代表覆盖。模拟每个截面放置砖头的情况后,可以发现不管怎么放,1的个数总是偶数,这可以用来化简。由于放置的特殊性,其实截面可以抽象成一个首尾可以相互影响的8位二进制数。如此,考虑所有情况,进行判断。

#include <cstdio>
#include<cstring>
#define mod 1000000007
#define LMT 130
#define LL long long
//~的优先级比位移低
//定义在结构体内就爆内存了..
//少在main中定义
//(x>>i)&1,才是判断啊
//给矩阵乘法跪了
using namespace std;
class matrix
{
    public:
    LL mat[LMT][LMT];
    int n,m;
    void init(void)
    {
        memset(mat,0,sizeof mat);
    }
    friend matrix operator*(matrix &,matrix &);
};
matrix matt,trans;
int state[260],lim=1<<8;
matrix operator *(matrix &a,matrix &b)
{
    matrix tem;
    tem.n=a.n;tem.m=b.m;
    tem.init();
    for(int k=0;k<a.m;k++)
      for(int i=0;i<a.n;i++)
      if(a.mat[i][k])
          for(int j=0;j<b.m;j++)
          tem.mat[i][j]=(tem.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
      return tem;
}
bool yes(int  code)
{
    int s=0;
    while(code)
    {
        s+=code&1;
        code>>=1;
    }
    return s%2==0;
}
LL can(int a,int b)
{
    int st,i,j;
    bool end=false;
    if(a==0)return b==255? 1LL:0;
    for(i=0;i<8;i++)
    {
        j=(i+7)%8;
        if((a&(1<<i))&&(a&(1<<j))==0)
        {
            st=i;
            break;
        }
    }
    for(i=st;i!=st||end==false;i=(i+1)%8)
    {
        end=true;
        j=(i+1)%8;
        if(0==(a&(1<<i)))
        {
            if(0==(b&(1<<i)))return 0;
        }
        else
        {
            if((a&(1<<j))&&(b&(1<<i))&&(b&(1<<j)))i++;
            else if((b&(1<<i))==0)continue;
            else return 0;
        }
    }
    return 1LL;
}
void init(void)
{
    lim=0;
    memset(state,-1,sizeof(state));
    for(int i=0;i<1<<8;i++)
    if(yes(i))state[i]=lim++;
    trans.init();
    trans.m=trans.n=lim;
    for(int i=0;i<1<<8;i++)
       for(int j=i+1;j<1<<8;j++)
       if(state[i]!=-1&&state[j]!=-1)
           trans.mat[state[j]][state[i]]=trans.mat[state[i]][state[j]]=can(i,j);
       trans.mat[lim-1][lim-1]=2;
}
matrix pow(matrix t,int n)
{
    matrix tem;
    tem.m=tem.n=lim;
    tem.init();
    for(int i=0;i<lim;i++)
    tem.mat[i][i]=1;
    while(n)
    {
        if(n&1)tem=tem*t;
        t=t*t;
        n>>=1;
    }
    return tem;
}
int main(void)
{
    int T,I,n;
    init();
   scanf("%d",&T);
    for(I=1;I<=T;I++)
    {
        scanf("%d",&n);
        matt=pow(trans,n);
        printf("Case %d: %I64d\n",I,matt.mat[lim-1][lim-1]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/cqlf__/article/details/8208648