首页 > 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


  1. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  2. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  3. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  4. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  5. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  6. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  7. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  8. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  9. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  10. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  11. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  12. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  13. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的

  14. 呵,说的是实情,租地主的地种收成还能明着对半分,地成国家的了,国家这个大地主可不象具本的小地主这么好说话,收成如何分就由不得农民了,哪个公社书记为了政冶任务放卫星高报虚报了产量,就要把收成全部上交国家还不够他凑数的,农民没就粮吃了,就饿死了,就这是当年的