upc 卡德加的兔子 线段树 + 矩阵快速幂
发布日期:2021-09-25 23:57:44
浏览次数:7
分类:技术文章
本文共 4213 字,大约阅读时间需要 14 分钟。
卡德加的兔子
时间限制: 5 Sec 内存限制: 128 MB题目描述
卡德加喜欢养兔⼦。他在达拉然的下⽔道⾥放了N个兔笼(编号1到N),⾥⾯养着他从德拉诺带来的兔⼦。它们的繁殖遵循斐波那契数列的规律:刚开始时,笼⼦⾥有⼀对刚出⽣的兔⼦。每对兔⼦在出⽣第⼆个⽉后,每个⽉都⽣⼀对兔⼦。(第⼀个⽉结束后有1对兔⼦。第⼆个⽉结束后有2对。) 卡德加从苏拉玛的⼤魔导⼠艾利桑德那边学习了先进的扭曲时空法术。 有时候,他会对⼀排连续的兔笼(从第L号到第R号)释放时光流逝法术,让这些兔笼⾥的时间前进K个⽉。另外⼀些时候,他想喂⼀下兔⼦,所以他想知道第L号到第R号兔笼⾥有多少只兔⼦。 (假设这些操作都是在⼀个⽉以内完成的,不需要考虑⾃然时间对兔⼦的影响。) 输入 第⼀⾏两个整数N;M,表⽰兔笼的数量和操作的数量。 接下来M⾏,每⾏包含三个数L;R;K。如果K>0,说明卡德加在使⽤时光流逝,编号L到R的兔笼时间前进K个⽉。如果K=0,说明他只是想喂兔⼦了,输出这些兔笼⾥有多少兔⼦。 输出 对每个喂兔⼦的操作,输出兔⼦的数量。答案模10007。 样例输入 Copy 100 100 26 85 0 2 81 1 67 69 0 22 69 2 27 80 0 79 87 2 57 63 2 76 80 3 95 99 4 45 94 2 27 75 1 22 75 0 12 51 2 25 66 2 11 61 1 83 88 0 27 83 1 14 97 1 71 90 3 10 44 4 73 93 4 1 98 4 23 93 3 56 76 3 13 25 2 57 68 1 18 28 3 19 28 0 21 78 4 10 95 3 93 98 4 73 81 0 28 44 0 20 53 0 59 75 4 53 69 2 9 54 1 55 95 4 14 46 4 22 50 2 35 98 3 34 93 4 91 92 4 43 53 2 45 64 2 58 87 4 64 74 3 36 62 4 16 98 0 71 76 3 39 99 1 6 16 3 12 73 2 37 82 4 56 92 1 81 99 0 9 51 3 27 80 4 13 60 3 24 39 0 13 17 1 46 54 0 81 84 4 45 61 1 21 87 0 12 61 1 52 98 0 25 64 2 3 68 0 61 64 0 24 45 4 16 53 2 23 59 3 68 86 4 55 74 1 68 74 4 22 87 1 5 21 1 3 89 1 5 84 2 18 58 1 47 81 3 74 80 1 54 71 0 9 16 2 29 55 4 12 85 1 49 84 0 30 71 3 50 51 0 51 51 0 2 38 0 14 92 3 5 31 1 5 53 1 34 83 1 29 69 0 34 82 2 50 93 1 83 96 2 样例输出 Copy 60 3 140 607 27 6408 1161 5444 7985 9779 9274 5261 9934 2118 9996 4133 2687 6932 7982 3829 2931 3078 8342 提示首先要做这个题,需要用矩阵快速幂来求第 n 项的斐波那契数列,因为矩阵乘法是有分配律的,所以当前进 k 天,也就是 { 1 , 1 }{ 1 , 0 } 的 k 次方 乘上原来线段树维护的矩阵值,以及懒标记的值,那么这个题就转换成了区间乘法了,唯一需要的一点就是掏出来个好的矩阵板子,以前没有存矩阵的板子,光这个板子就卡了我半天。
注意一下懒标的初始值设为 单位矩阵,区间和 设位 fib2矩阵({ 1 , 0 }{ 0 , 0 }) ,mp[ 0 ] [ 0 ]这个位置就是斐波那契的第1项,因为题意可知初始的时候都应该是第一项。 pushdown的时候注意 哪个矩阵乘上哪个矩阵,矩阵乘法是没有交换律的,乘反了答案肯定是不对的。 套上板子之后,心情就变得愉悦起来了 ~ 一开始还想用斐波那契数列模数有循环节打个表来做,结果这样的方法只能支持单点修改,修改一个区间是不现实的。。 改下代码,尽量变得可读性高一点吧,写的太丑了。。#include#include #include #include #include
转载地址:https://blog.csdn.net/DaNIelLAk/article/details/105924317 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年03月05日 17时55分32秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
oracle自己运行,创建Oracle自动执行Job
2019-04-21
chmod 赋权所有_chmod 权限 命令详细用法
2019-04-21
html代码翻译_[译]您知道 HTML 的键盘标签吗?
2019-04-21
html抽奖代码_JavaScript高手之路:封装抽奖效果
2019-04-21
的流程图做完后如何保存_2019超火的半永久眉是哪款?做完后我们如何护理?...
2021-06-24
去除logo 高德地图api_深圳品牌logo升级如何保持原型的同时更具创新?
2021-06-24
二重积分转换成极坐标_二重积分转换极坐标r的范围如何确定?
2021-06-24
python中倒背如流_八字基础知识--倒背如流篇
2021-06-24
以太坊地址和公钥_以太坊地址是什么
2021-06-24
npm 不重启 全局安装后_解决修复npm安装全局模块权限的问题
2021-06-24
vs格式化json 不生效_vs code 格式化 json 配置
2021-06-24
go 字符串反序列化成对象数组_Fastjson 1.2.24反序列化漏洞深度分析
2021-06-24
hibernate mysql 缓存_hibernate和mysql的缓存问题,没辙了!
2021-06-24
abp框架 mysql_ABP框架使用Mysql数据库
2021-06-24
mysql树形递归删除_使用递归删除树形结构的所有子节点(java和mysql实现)
2019-04-21
linux mysql 不能连接远程_linux mysql 远程连接
2019-04-21