首页 > 代码库 > hihocoder#1143 : 骨牌覆盖问题·一
hihocoder#1143 : 骨牌覆盖问题·一
#1143 : 骨牌覆盖问题·一
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：
我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？
举个例子，对于长度为1到3的棋盘，我们有下面几种覆盖方式：
提示：骨牌覆盖
提示：如何快速计算结果
输入
第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000
输出
第1行：1个整数，表示覆盖方案数 MOD 19999997
- 样例输入
62247088
- 样例输出
17748018
/*fibonacci数列... */#include<cstdio>#include<cstring>using namespace std;typedef long long ll;const ll mod=19999997;ll n;struct matrix{ll s[2][2];}A,F;matrix operator *(const matrix &a,const matrix &b){ matrix c; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ c.s[i][j]=0; for(int k=0;k<2;k++){ c.s[i][j]+=a.s[i][k]*b.s[k][j]; c.s[i][j]%=mod; } } } return c;}matrix fpow(matrix a,ll p){ matrix ans; for(int i=0;i<2;i++)for(int j=0;j<2;j++) ans.s[i][j]=(i==j); for(;p;p>>=1,a=a*a) if(p&1) ans=ans*a; return ans;}int main(){ scanf("%lld",&n); F.s[0][0]=1;F.s[0][1]=F.s[1][0]=F.s[1][1]=0; A.s[0][0]=A.s[0][1]=A.s[1][0]=1;A.s[1][1]=0; F=fpow(A,n)*F; printf("%lld\n",F.s[0][0]); return 0;}
hihocoder#1143 : 骨牌覆盖问题·一
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。