hihoCode #1151 : 骨牌覆盖问题·二
覆盖 183 问题
2023-09-11 14:15:28 时间
#1151 : 骨牌覆盖问题·二
Time Limit:10000ms
Case Time Limit:1000ms
Memory Limit:256MB
描述
上一周我们研究了2xN的骨牌问题,这一周我们不妨加大一下难度,研究一下3xN的骨牌问题?
所以我们的题目是:对于3xN的棋盘,使用1x2的骨牌去覆盖一共有多少种不同的覆盖方法呢?
首先我们可以肯定,奇数长度一定是没有办法覆盖的;对于偶数长度,比如2,4,我们有下面几种覆盖方式:
输入
第1行:1个整数N。表示棋盘长度。1≤N≤100,000,000
输出
第1行:1个整数,表示覆盖方案数 MOD 12357
- Sample Input
-
62247088
- Sample Output
-
4037
解题:造转移方程1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL mod = 12357; 5 struct Matrix{ 6 int m[8][8]; 7 Matrix(){ 8 init(); 9 } 10 void init(){ 11 memset(m,0,sizeof m); 12 } 13 Matrix operator*(const Matrix &rhs){ 14 Matrix ret; 15 for(int k = 0; k < 8; ++k) 16 for(int i = 0; i < 8; ++i) 17 for(int j = 0; j < 8; ++j) 18 ret.m[i][j] = (ret.m[i][j] + m[i][k]*rhs.m[k][j])%mod; 19 return ret; 20 } 21 void print(){ 22 for(int i = 0; i < 8; ++i){ 23 for(int j = 0; j < 8; ++j) 24 printf("%d ",m[i][j]); 25 cout<<endl; 26 } 27 } 28 }; 29 Matrix a,b; 30 void quickPow(LL index){ 31 while(index){ 32 if(index&1) a = a*b; 33 index >>= 1; 34 b = b*b; 35 } 36 } 37 bool tab[10][10]; 38 void dfs(int cur,int st){ 39 if(cur >= 3){ 40 int ss = 0; 41 for(int i = 2; i >= 0; --i){ 42 ss <<= 1; 43 ss |= tab[i][1]; 44 } 45 b.m[st][ss]++; 46 return; 47 } 48 if(!tab[cur][0]){ 49 if(!tab[cur][1]){ 50 tab[cur][0] = tab[cur][1] = true; 51 dfs(cur+1,st); 52 tab[cur][0] = tab[cur][1] = false; 53 } 54 if(cur + 1 < 3){ 55 if(!tab[cur+1][0]){ 56 tab[cur+1][0] = tab[cur][0] = true; 57 dfs(cur+2,st); 58 tab[cur+1][0] = tab[cur][0] = false; 59 } 60 } 61 }else dfs(cur + 1,st); 62 } 63 void init(int st){ 64 memset(tab,false,sizeof tab); 65 for(int i = 0,xst = st; i < 3; ++i,xst >>= 1) 66 tab[i][0] = xst&1; 67 dfs(0,st); 68 } 69 int main(){ 70 int n; 71 while(~scanf("%d",&n)){ 72 b.init(); 73 a.init(); 74 for(int i = 0; i <= 7; ++i) init(i); 75 a.m[0][0] = 1; 76 quickPow(n); 77 printf("%d\n",a.m[0][0]); 78 } 79 return 0; 80 }
相关文章
- win7环境下,vagrant,在启动虚拟机的时候报错io.rb:32:in `encode': incomplete "xC8" on GBK (Encoding::InvalidByteSequenceError)
- Cannot find module '@babel/core'
- HDU5518 : John's Fences
- 解决ERROR 2003 (HY000): Can't connect to MySQL server on 'localhost:3306' (10061)问题
- HDU 5023 A Corrupt Mayor's Performance Art (据说是线段树)
- 文章爬取Bot😎-公众号,知乎,知乎专栏,简书,知否(SegmentFault),掘金,CSDN,V2EX,博客园文章转为 markdown
- nested exception is org.xml.sax.SAXParseException; lineNumber: 8; columnNumber: 56; cvc-complex-type.2.4.c通配符的匹配很全面, 但无法找到元素 'dubbo:application' 的声明
- adbl连接不上 daemon not running. starting it now on port 5037 ADB server didn't ACK
- Solve error: 'Qt::WFlags' has not been declared
- WebLogic: The Definitive Guide examined WebLogic's security mechanisms--reference