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
#include
#include
#include
#include
#include
#include
#include
#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
PII;const int N=100010,M=2,mod=10007,INF=0x3f3f3f3f;const double eps=1e-6;struct Mat{ int r,c,mp[5][5]; Mat(){ memset(mp,0,sizeof mp); }//构建0矩阵 void build_one()//构建单位矩阵 { memset(mp,0,sizeof mp); mp[0][0]=mp[1][1]=1; } void build_fib1()//构建{1,1}{1,0} { mp[1][0]=mp[0][1]=mp[0][0]=1; mp[1][1]=0; } void build_fib2()//构建{1,0}{0,0} { mp[0][0]=1; mp[1][0]=mp[1][1]=mp[0][1]=0; } Mat operator * (Mat m) const//矩阵乘法 { Mat ans; memset(ans.mp,0,sizeof ans.mp); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) { ans.mp[i][j]+=(mp[i][k]*m.mp[k][j])%mod; ans.mp[i][j]%=mod; } return ans; } Mat operator + (Mat m) const//矩阵加法 { Mat ans; for(int i=0;i<2;i++) for(int j=0;j<2;j++) ans.mp[i][j]=(mp[i][j]+m.mp[i][j])%mod; return ans; } friend Mat operator ^ (Mat m,int b)//矩阵快速幂 { Mat ans; ans.build_one(); while(b) { if(b&1) ans=ans*m; m=m*m; b>>=1; } return ans; }};struct Node{ int l,r,flag;//flag表示b是否需要往下传 Mat a,b;//a 是和 b 是懒标 }tr[N<<2];int n,m;void pushup(int u){ tr[u].a=tr[L].a+tr[R].a;}void pushdown(int u){ if(!tr[u].flag) return; tr[L].b=tr[u].b*tr[L].b,tr[R].b=tr[u].b*tr[R].b;//更新儿子的懒标 tr[L].a=tr[u].b*tr[L].a,tr[R].a=tr[u].b*tr[R].a;//更新儿子的和 tr[u].flag=0,tr[L].flag=tr[R].flag=1;//更新标记 tr[u].b.build_one();//将懒标设位单位矩阵 }void build(int u,int l,int r){ Mat x,y; y.build_one(); tr[u]={ l,r,0}; tr[u].b.build_one(); if(l==r) { tr[u].a.build_fib2(); return; } build(L,l,mid),build(R,mid+1,r); pushup(u);}void modify(int u,int l,int r,Mat c){ if(tr[u].l>=l&&tr[u].r<=r) { tr[u].flag=1; tr[u].a=c*tr[u].a; tr[u].b=c*tr[u].b; return; } pushdown(u); if(l<=mid) modify(L,l,r,c); if(r>mid) modify(R,l,r,c); pushup(u);}int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].a.mp[0][0]%mod; pushdown(u); int x=0; if(l<=mid) x=(x+query(L,l,r))%mod; if(r>mid) x=(x+query(R,l,r))%mod; return x%mod;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); Mat temp; temp.build_fib1(); cin>>n>>m; build(1,1,n); while(m--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); if(k) modify(1,l,r,temp^k); else printf("%d\n",query(1,l,r)%mod); } return 0;}/**/

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/105924317 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:魔法石 尺取
下一篇:upc 小y的序列

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月05日 17时55分32秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

oracle自己运行,创建Oracle自动执行Job 2019-04-21
oracle报错00020,oracle启动 ORA-00020: maximum number of processes (%s) exceeded错误 2019-04-21
chmod 赋权所有_chmod 权限 命令详细用法 2019-04-21
html代码翻译_[译]您知道 HTML 的键盘标签吗? 2019-04-21
html抽奖代码_JavaScript高手之路:封装抽奖效果 2019-04-21
hadoop 3.3 一直停留在running wordcount_蛋价持续下跌,今日跌破3.3元大关!深秋季节价格还能反弹吗?... 2019-04-21
的流程图做完后如何保存_2019超火的半永久眉是哪款?做完后我们如何护理?... 2021-06-24
去除logo 高德地图api_深圳品牌logo升级如何保持原型的同时更具创新? 2021-06-24
二重积分转换成极坐标_二重积分转换极坐标r的范围如何确定? 2021-06-24
python中倒背如流_八字基础知识--倒背如流篇 2021-06-24
以太坊地址和公钥_以太坊地址是什么 2021-06-24
linux查看wifi信号命令_linux – 获取WIFI信号强度 – 寻求最佳方式(IOCTL,iwlist(iw)等)... 2021-06-24
npm 不重启 全局安装后_解决修复npm安装全局模块权限的问题 2021-06-24
vs格式化json 不生效_vs code 格式化 json 配置 2021-06-24
go 字符串反序列化成对象数组_Fastjson 1.2.24反序列化漏洞深度分析 2021-06-24
onmessage websocket 收不到信息_WebSocket断开重连解决方案,心跳重连实践 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