正文

矩阵幂求解骨牌覆盖数(soj3021)(代码片段)

clearmoonlight  clearmoonlight  2023-03-18  435

关键词：

题意：给出$4 imes N$的矩形以及尺寸为$2 imes 1$的骨牌，求解该矩形能被骨牌覆盖的种数。

分析：起初我自己一直尝试推导出一个递推式，但是一直没有成功。后来看了网上别人给的递推式：$f(n)=f(n-1)+5*f(n-2)+f(n-3)-f(n-4)$，有了这个式子，这个题很好求解了。下面我介绍一种其他的方法。将矩形看作$N imes 4$, 铺骨牌到第$i$行有$6$种情况：$XXXX$, $XOOX$, $OXXO$, $XXOO$, $OOXX$, $OOOO$, 其中$X$表示有骨牌，$O$表示没有骨牌。定义$f(i,1)$, $f(i,2)$, $f(i,3)$, $f(i,4)$, $f(i,5)$, $f(i,6)$分别为上述6种情形的种类数，则我们可以得到以下递推关系：

$f(i+1,1)=f(i,1)+f(i,3)+f(i,4)+f(i,5)+f(i,6)$

$f(i+1,2)=f(i,3)$

$f(i+1,3)=f(i,1)+f(i,2)$

$f(i+1,4)=f(i,1)+f(i,5)$

$f(i+1,5)=f(i,1)+f(i,4)$

$f(i+1,6)=f(i,1)$

矩阵形式为：

$left[eginarraycf(i+1, 1) f(i+1, 2) f(i+1, 3) f(i+1, 4) f(i+1, 5) f(i+1, 6)endarray ight]=left[eginarraycccccc1 &0 &1 &1 &1 &1 0 &0 &1 &0 &0 &0 1 &1 &0 &0 &0 &0 1 &0 &0 &0 &1 &0 1 &0 &0 &1 &0 &0 1 &0 &0 &0 &0 &0 endarray ight]left[eginarraycf(i, 1) f(i, 2) f(i, 3) f(i, 4) f(i, 5) f(i, 6)endarray ight]$. 下面的问题即转化成了矩阵的快速幂算法。

代码：

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 int N, M;
 5 struct matrix
 6 
 7     int P[7][7];
 8     matrix()
 9     
10         memset(P, 0, sizeof(P));
11     
12 ;
13 matrix matMul(matrix A, matrix B)
14 
15     matrix C;
16     int i, j, k;
17     for (i = 1; i <= 6; i++)
18         for (j = 1; j <= 6; j++)
19             for (k = 1; k <= 6; k++)
20                 C.P[i][j] = (C.P[i][j] + A.P[i][k] * B.P[k][j]) % M;
21     return C;
22 
23 matrix matPow(matrix M)
24 
25     matrix Res;
26     int i;
27     for (i = 1; i <= 6; i++)
28         Res.P[i][i] = 1;
29     int k = N - 1;
30     while (k)
31     
32         if (k & 1)
33             Res = matMul(Res, M);
34         k >>= 1;
35         M = matMul(M, M);
36     
37     return Res;
38 
39 int main()
40 
41     matrix Con,Ans;
42     Con.P[1][1] = Con.P[1][3] = Con.P[1][4] = Con.P[1][5] = Con.P[1][6] = 1;
43     Con.P[2][3] = 1;
44     Con.P[3][1] = Con.P[3][2] = 1;
45     Con.P[4][1] = Con.P[4][5] = 1;
46     Con.P[5][1] = Con.P[5][4] = 1;
47     Con.P[6][1] = 1;
48     while (scanf("%d%d", &N, &M) == 2 && N > 0)
49     
50         Ans = matPow(Con);
51         printf("%d
", (Ans.P[1][1] + Ans.P[1][3] + Ans.P[1][4] + Ans.P[1][5] + Ans.P[1][6])%M);
52     
53     return 0;
54

View Code

p2070-骨牌覆盖

...7的值。SampleInput2SampleOutput3Hint1<=n<=100000000Source递推，矩阵快速幂这题先通过打表找出递推规律，然后推出转移矩阵，使用矩阵快速幂即可。 1#incl 查看详情

骨牌覆盖小结

题目链接棋盘规模2*n （n很大）直接找出递推公式用矩阵快速幂求解#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=2;constLLmod=19999997;LLb[N]={1,1};//此处初始化列向量LLhh[N][N]={{1,1},{1,0}};structMat{LLmat[N 查看详情

骨牌覆盖快速幂

http://www.cnblogs.com/easonliu/p/4419459.html输入第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000输出第1行：1个整数，表示覆盖方案数MOD19999997样例输入62247088样例输出17748018 当N很小的时候，我们直接通过递推公式便可以计算。当N很... 查看详情

区间动态规划-dfs种类数(soj2469)(代码片段)

...我们可以写出它的深搜结果，现在给出深搜结果字符串$S$求解对应树的种类数。例子：深搜结果:$ABABABA$,对应的树(根结点在底层)有$5$个。分析：应用区间动态规划，定义$dp[i][j]$为$S[i..j]$对应的树的个数，则分两类：(1)$S[i]$有一... 查看详情

[递推+矩阵快速幂]codeforces1117d-magicgems(代码片段)

...时间复杂度是要上天的我们可以把递推式求解转化成矩阵乘法求解 3.套用矩阵快速幂的板子，加速计算参考代码：#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_____ios::sync_with_stdio(false);cin.tie(0);constintM=1e9+7;/... 查看详情

hdu3292佩尔方程求解&&矩阵快速幂(代码片段)

任意门：http://acm.hdu.edu.cn/showproblem.php?pid=3292Nomoretricks,MrNanguoTimeLimit:3000/1000MS(Java/Others) MemoryLimit:65535/32768K(Java/Others)TotalSubmission(s):587 AcceptedSubmission(s):400ProblemDescriptionNowSailormoongirlswanttotellyouaancie... 查看详情

矩阵快速幂(代码片段)

一、前期铺垫　在讲矩阵快速幂之前，我们先来看一下整数快速幂。求X的N次方。　举个例子，在求x^19时，我们可以拆分成x^16、x^2和x的乘积。我们观察19的二进制数（10011），发现二进制第i位上的值为1，在乘积中就要有x的2^i的... 查看详情

poj2411轮廓线dp裸题(代码片段)

题意:用12的骨牌覆盖nm的矩阵的方案数题解:dp[i][j]表示枚举到了第i行,j状态的方案数,三种转移,向上的,要求不是第一行而且上面的没有覆盖过,向下的,要求不是第一列而且左边没有覆盖过,不放,要求上面没有覆盖过//#pragmacomment(link... 查看详情

hihocoder#1162矩阵加速dp

#1162:骨牌覆盖问题·三时间限制:10000ms单点时限:1000ms内存限制:256MB描述前两周里，我们讲解了2xN,3xN骨牌覆盖的问题，并且引入了两种不同的递推方法。这一次我们再加强一次题目，对于给定的K和N，我们需要去求KxN棋盘的覆... 查看详情

最大子矩阵(soj3329)(代码片段)

SOJ3329:MaximumSubmatrixIIhttp://acm.scu.edu.cn/soj/problem.action?id=3329Problem:Givena$0-1$matrix,findthemaximumsubmatrixwhichcontainsonly0sandoutputthenumberof0sinit. Technique:(1)DynamicProgrammingDenote$dp[i][j],1leilen,1lejlem$asthemaximumnumberofsequential0sendedat$[i,j]$,thenthenumberof... 查看详情

六省联考2017组合数问题题解（矩阵快速幂优化dp）(代码片段)

题目链接题目大意：求$(sumlimits_i=0^nC_nk^ik+r)modp$的值。---------------------讲真，一开始看到这个题我都没往DP方面想，以为是什么大力推式子的数学题。设$f_i,j$表示考虑前$i$个物品，选出的物品$modk=j$的方案数。最后输出$f_n,r$。易... 查看详情

快速幂求解

...需要这个算法，注意它不但可以对数求次幂，而且可用于矩阵快速幂。把b转换成二进制数，该二进制位数有logb位；该二进制数第i位的权为2i-1 例如： 11的二进制是1011 查看详情

poj3734blocks（矩阵快速幂+矩阵递推式）(代码片段)

题意：个n个方块涂色，只能涂红黄蓝绿四种颜色，求最终红色和绿色都为偶数的方案数。该题我们可以想到一个递推式。设a[i]表示到第i个方块为止红绿是偶数的方案数，b[i]为红绿恰有一个是偶数的方案数，c[i]表示红绿都... 查看详情

快速幂矩阵(代码片段)

整数快速幂：为了引出矩阵的快速幂，以及说明快速幂算法的好处，我们可以先求整数的幂。如果现在要算X^8：则XXXXXXXX按照寻常思路，一个一个往上面乘，则乘法运算进行7次。(XX)(XX)(XX)(XX)这种求法，先进行乘法得X^2,然后对X^2... 查看详情

hdu-1757asimplemathproblem---矩阵快速幂模板题(代码片段)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1757题目大意：求递推式第k项模mIfx<10f(x)=x.Ifx>=10f(x)=a0*f(x-1)+a1*f(x-2)+a2*f(x-3)+……+a9*f(x-10);Andai(0<=i<=9)canonlybe0or1.解题思路：构建矩阵直接用矩阵快速幂模板求解注意，小于查看详情

codeforces576dflightsforregularcustomers矩阵快速幂(看题解)(代码片段)

FlightsforRegularCustomers 临接矩阵的k次就是恰好走k步从i走到j的方案数，方案数在这里并不关键，所以可以把它变成01矩阵。一个很直观的想法是用二分取check它，但是这并不单调。。然后就不会了。。我们可以把G[n-1][n-1]变... 查看详情

省选算法学习-矩阵与矩阵快速幂(代码片段)

0x00引入矩阵，顾名思义，就是由数构成的矩形阵列比如这样的：$\beginarrayl\beginbmatrix2&3&4\0&7&13\c&\alpha&\sqrt5\endbmatrix\\endarray$就是一个3*3的矩阵矩阵在信息学乃至数学里面的用处都非常广泛，下面就来介绍下它的... 查看详情

51nod1031骨牌覆盖|fibonacci

...;Mod 10^9 + 7Input示例3Output示例3思路：对于第x块骨牌的情况，我们用a[x]表示其方法数；其比x-1块骨牌时多了一块骨牌，多出的骨牌有两种放法：１．我们可以直接将其竖着添加在最末端，那么其排列数就为就是前x-1块... 查看详情