加载中…
正文 字体大小:

poj 3420 Quad Tiling 矩阵乘法+快速求幂

(2011-10-13 15:11:48)
标签:

it

分类: 矩阵乘法
题意:用1 X 2的矩形填充4 X n的矩形,共有多少种不同方法。
思路:网上的代码大部由状态压缩与矩阵乘法的结合,这里给大家说一由递推+矩阵乘的方法。
我们把4当作列数,n当作行数。当第n行填满时,第(n+1)行会出现以下几种情况:poj <wbr>3420 <wbr>Quad <wbr>Tiling <wbr>矩阵乘法+快速求幂
情况a为第n行刚好填满且没有突出到第(n+1)行,即为所求答案,由图不难推出:
a[n] = a[n-1] + b[n-1] + c[n-1] + dx[n-1] + dy[n-1];
b[n] = a[n-1];
c[n] = a[n-1] + e[n-1];
dx[n]= a[n-1] + dy[n-1];
dy[n]= a[n-1] + dx[n-1];
e[n] = c[n-1].
令d[n] = dx[n] + dy[n],则
a[n] = a[n-1] + b[n-1] + c[n-1] + d[n-1];
b[n] = a[n-1];
c[n] = a[n-1] + e[n-1];
d[n] = a[n-1] * 2 + d[n-1];
e[n] = c[n-1].
令A[n] = { a[n] , b[n] , c[n] , d[n] , e[n] },则有:
A[n] =  A[n-1] X F
                                               0 \
                                               0 |
     ={ a[n-1] b[n-1] c[n-1] d[n-1] e[n-1] } X |  1 |
                                               0 |
                                               0 /
那么A[x] = A[y] X F^(x-y),其中 x >= y,即有 A[n] = A[0] X F^n 。
由每种状态不难看出 A[0] = { 1 , 0 , 0 , 0 , 0 }。
那么就可以用矩阵乘法+快速求幂先算出 F^n,则 F^n 的第一列的和与a[0]的乘积即为答案。
  1. #include<stdio.h>
  2. int m;
  3. void mult(int a[][6],int b[][6])
  4. {
  5.     int i,j,k,s[6][6];
  6.     for(i=1;i<6;i++)
  7.     {
  8.         for(j=1;j<6;j++)
  9.             s[i][j]=0;
  10.     }
  11.     for(i=1;i<6;i++)
  12.     {
  13.         for(k=1;k<6;k++)
  14.         {
  15.             if(a[i][k]==0)
  16.                 continue;
  17.             for(j=0;j<6;j++)
  18.                 s[i][j]=(s[i][j]+a[i][k]*b[k][j]%m)%m;
  19.         }
  20.     }
  21.     for(i=1;i<6;i++)
  22.         for(j=1;j<6;j++)
  23.             b[i][j]=s[i][j]%m;
  24. }
  25. int main()
  26. {
  27.     int i,j,n,a[6],b[6][6],x[6][6],y[6][6],s;
  28.     for(i=1;i<6;i++)
  29.     {
  30.         for(j=1;j<6;j++)
  31.             b[i][j]=0;
  32.         a[i]=0;
  33.     }
  34.     a[1]=1;
  35.     b[1][4]=2;
  36.     b[1][1]=b[2][1]=b[3][1]=1;
  37.     b[4][1]=b[1][2]=b[1][3]=1;
  38.     b[5][3]=b[4][4]=b[3][5]=1;
  39.     while(scanf("%d%d",&n,&m),n||m)
  40.     {
  41.         for(i=1;i<6;i++)
  42.         {
  43.             for(j=1;j<6;j++)
  44.             {
  45.                 x[i][j]=b[i][j];
  46.                 y[i][j]=0;
  47.             }
  48.             y[i][i]=1;
  49.         }
  50.         while(n>0)
  51.         {
  52.             if(n&1)mult(x,y);
  53.             n>>=1;
  54.             mult(x,x);
  55.         }
  56.         for(s=0,i=1;i<6;i++)
  57.             s=(s+a[i]*y[i][1]%m)%m;
  58.         printf("%d\n",s);
  59.     }
  60.     return 0;
  61. }

0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有