状态压缩+矩阵乘法hdu-4332-Constructing Chimney

时间：2024-01-14 21:35:50

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4332

题目意思：

用1*1*2的长方体构造一个中间为空的底面3*3的立体烟囱。

解题思路：

实际上就是poj上这道题的升华版。推荐先做那道题。

只不过本题的每一层相当于poj上那题的每一行，此题层数很多，所以很直白的想到用矩阵快速幂加速。

这类型的矩阵乘法做的比较少。

用二维矩阵表示两层之间的转移关系，第一维表示上一层的状态，第二维表示下一层的状态，作为基矩阵。每次乘以它就相当于加了一层。状态图和矩阵转移如下，虽然很丑，但还看的清。

0表示当前层不放，那么它下面的一层肯定要为1（并且还是竖着的1），

1表示当前层放，可以是平着，也可以是竖着。（最后在统计最后一层平放的情况，最后一层竖着放肯定不行，超过了）

因为要多次调用基矩阵的偶次方，故预处理给保存起来。

状态压缩+矩阵乘法hdu-4332-Constructing Chimney

代码：

#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;

}

相关文章