HDU 2842 Chinese Rings( 递推关系式 + 矩阵快速幂 )
2024-09-06 21:31:31
链接:传送门
题意:解 N 连环最少步数 % 200907
思路:对于 N 连环来说,解 N 连环首先得先解 N-2 连环然后接着解第 N 个环,然后再将前面 N-2 个环放到棍子上,然后 N 连环问题变成了 N-1 连环问题,然后将递推关系式化成矩阵形式然后用矩阵快速幂解决就ok了
- 递推关系式:Fn = Fn-1 + 2 * Fn-2 + 1
/*************************************************************************
> File Name: hdu2842.cpp
> Author: WArobot
> Blog: http://www.cnblogs.com/WArobot/
> Created Time: 2017年05月03日 星期三 22时59分07秒
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
const int MOD = 200907;
const int maxn = 3;
#define ll long long
#define mod(x) ((x)%MOD)
struct mat{
ll m[maxn][maxn];
}unit;
mat operator*(mat a,mat b){
mat ret;
ll x;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
x = 0;
for(int k=0;k<3;k++)
x += mod( (ll)(a.m[i][k]*b.m[k][j] ));
ret.m[i][j] = x;
}
}
return ret;
}
mat pow_mat(mat a,ll x){
mat ret = unit;
while(x){
if(x&1) ret = ret*a;
a = a*a;
x >>= 1;
}
return ret;
}
void init_unit(){
for(int i=0;i<3;i++) unit.m[i][i] = 1;
return;
}
ll n;
mat a,b;
void init(){
memset(a.m,0,sizeof(a.m));
memset(b.m,0,sizeof(b.m));
a.m[0][0] = 1; a.m[0][1] = 2; a.m[0][2] = 1; a.m[1][0] = 1; a.m[2][2] = 1;
b.m[0][0] = 2; b.m[1][0] = 1; b.m[2][0] = 1;
}
int main(){
init();
init_unit();
int ss[4] = {1,1,2,5};
while(cin>>n && n){
if(n<=3) printf("%d\n",ss[n]);
else{
mat ans = pow_mat(a,n-2);
ans = ans*b;
cout<< ans.m[0][0]%MOD <<endl;
}
}
return 0;
}
最新文章
- 第一章 MYSQL的架构和历史
- web测试方法
- iPhone 6/6 Plus国行版开卖当日抢购攻略
- windows快捷操作
- iOS 自动布局总结
- UE4学习笔记(三): 为什么使用C++替代UnrealScript?
- JSU省赛队员选拔赛个人赛1(Coin Change、Fibbonacci Number、Max Num、单词数、无限的路、叠筐)
- find: paths must precede expression(转)
- java获取真实ip
- 2.Cocos2d-x-3.2编写3d打飞机,项目代码总结
- oracle 事务 与 提交
- cisco4507引擎模式切换
- BZOJ1324Exca王者之剑&;BZOJ1475方格取数——二分图最大独立集
- Web Scraper爬取就是这么简单
- JS 实现 jQuery的$(function(){});
- ORM--Entity Framework 学习(01)
- wc.java
- ko内核模块文件以及载入模块命令modprobe insmod
- sql server 查询分析器中表名无效,有红线,其实是这张表的
- flashback query闪回数据
热门文章
- 数据结构(3) 第三天 栈的应用:就近匹配/中缀表达式转后缀表达式 、树/二叉树的概念、二叉树的递归与非递归遍历(DLR LDR LRD)、递归求叶子节点数目/二叉树高度/二叉树拷贝和释放
- 【JavaScript框架封装】实现一个类似于JQuery的内容框架的封装
- jquery ajax 全介绍
- P3375 【模板】KMP字符串匹配 (KMP模板)
- 获取Linux ip
- matplotlib 显示两张图片,折线图 和 scipy
- 通过腾讯地图api获取用户位置限制在指定位置区域
- ZOJ 3888 Twelves Monkeys
- 数据库-mongodb-索引
- 2015.04.21,外语,读书笔记-《Word Power Made Easy》 12 “如何奉承朋友” SESSION 32