题解、Writeup、游记和碎碎念
包含标签 暴力 的文章
农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。
问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 n 个月有多少只兔子？
聪明的你可能已经发现，第 n 个月的兔子数正好是第 n 个 Fibonacci(斐波那契)数。栋栋不懂什么是 Fibonacci 数，但他也发现了规律：第 i+2 个月的兔子数等于第 i 个月的兔子数加上第 i+1 个月的兔子数。前几个月的兔子数依次为：
1 1 2 3 5 8 13 21 34 …
栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。
每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每 k 对兔子围成一圈，最后剩下的不足 k 对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。
我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当 k=7 时，前几个月的兔子数依次为： 1 1 2 3 5 7 12 19 31 49 80 …
给定 n，你能帮助栋栋计算第 n 个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第 n 个月的兔子对数除 p 的余数即可。
给一个长为 n 的序列 a，每个数在 0 到 v - 1 之间，有 m 次操作。
操作 1：每次询问一个区间中是否可以选出两个下标的集合 X，Y，满足：
1.X 和 Y 没有交集 2.设集合 X 中有一个元素是 i，则其对集合 X 的贡献是 a[i] + 1，要求集合 X 的元素的总贡献和集合 Y 的元素的总贡献
相等如果可以选出这两个集合，输出 Yuno 否则输出 Yuki
操作 2：修改一个区间 l,r 之间的数，使得所有 l <= i <= r，a[i] = a[i] * a[i] * a[i] % v ，即区间立方
XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。 "第一分钟，X 说，要有数列，于是便给定了一个正整数数列。 第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。 第四分钟，彩虹喵说，要是 noip 难度，于是便有了数据范围。 第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。 第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 64 位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。" ——《上帝造题的七分钟·第二部》 所以这个神圣的任务就交给你了。