| 题目名称 | 2498. [SYZOJ 218]小L的斐波那契数列游戏 |
|---|---|
| 输入输出 | chenyao_fib_game.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 sxysxy
于2016-10-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：35， 提交：74， 通过率：47.3% | ||||
 Fmuckss |
100 | 0.253 s | 1.46 MiB | C++ |
 HeHe |
100 | 0.297 s | 0.83 MiB | C++ |
|
Fmuckss |
100 | 0.343 s | 1.46 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.352 s | 1.49 MiB | C++ |
|
哒哒哒哒哒 |
100 | 0.375 s | 1.49 MiB | C++ |
 安呐一条小咸鱼。 |
100 | 0.432 s | 2.96 MiB | C++ |
 KCkwok |
100 | 0.454 s | 0.47 MiB | C++ |
 Sky_miner |
100 | 0.459 s | 0.48 MiB | C++ |
|
Sky_miner |
100 | 0.460 s | 0.48 MiB | C++ |
 MistyEye |
100 | 0.464 s | 0.46 MiB | C++ |
| 本题关联比赛 | |||
| 防止浮躁的小练习v0.4 | |||
| 关于 小L的斐波那契数列游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
菲波那切数列递归算法怎么写
38sn
2021-12-14 18:45
17楼
| ||||
|
分块秒过。。
| ||||
|
| ||||
|
为什么一个log的线段树做法这么慢？
话说把转移矩阵离线了不就掉了一个log吗？ | ||||
|
果然不开栈就10分。。
感谢楼上大神和5楼与12楼的两位大神教我如何手工开栈过这道题！ 另外，2楼大神还教了我如何用树套树主席树来做，但我太辣鸡了，没有学会！  _Itachi
2016-10-15 06:14
13楼
| ||||
|
强行线段树。
| ||||
|
%楼上开栈代码，%楼上Titwct
| ||||
|
| ||||
|
树套主席树秒之
TreeInTreeWithChairmanTree | ||||
|
%楼下开栈代码，%楼下Titwct
| ||||
FoolMike
蠢丶蛋蛋蛋蛋
YGOI_真神名曰驴蛋蛋2498. [SYZOJ 218]小L的斐波那契数列游戏
★★★ 输入文件：chenyao_fib_game.in
输出文件：chenyao_fib_game.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
斐波那契数列是这样的一个数列
Fib[1] = 1
Fib[2] = 1
从Fib[3]开始满足Fib[n] = Fib[n-1]+Fib[n-2]
小L忽然对斐波那契数列着迷了呢。最开始小L有个长度为N，值全部为0的数列。之后小L可能会让数列下标[l, r]区间内的数，分别加上Fib[1], Fib[2], Fib[3]...Fib[1+r-l]。她还会时不时地查看数列中第p个数是多少。但是小L每次只有1s的时间玩这个好玩的游戏，你能帮帮她快速地完成这个游戏吗？
【输入格式】
第一行两个整数n. m，表示数列长度为n，小L会进行m个操作
下面m行，每行有一个操作。如果第一个数为0，后面跟一个数p，表示查询数列中第p个的值。如果第一个数为1，后面跟两个数l ,r。表示数列下标[l, r]范围内的数加上题面所述的斐波那契数列。
【输出格式】
对于每个询问操作输出其正确结果。由于这个结果可能非常大，只需输出其对 998244353 取模的结果。
【样例输入】
5 8 1 1 3 1 2 5 0 3 0 5 0 1 1 1 5 0 4 0 5
【样例输出】
3 3 1 5 8
【提示】
对于样例的解释:
原始序列
0 0 0 0 0
修改操作[1,3]后
1 1 2 0 0
修改操作[2,5]后
1 2 3 2 3
查询3
输出3
查询5
输出3
查询1
输出1
修改操作[1,5]后
2 3 5 5 8
查询4
输出5
查询5
输出8
【数据范围】
n <= 10000
m <= 100000
数据随机生成，查询与修改操作比例约为1:1
输入文件共约11mb
泥萌意识到小L是谁了吗23333
【来源】
sxysxy