#P11772. 报社天狗
报社天狗
题目背景
因为天依想不到新歌歌词怎么写破防了,所以这题的主人公不是天依。
题目描述
新一期《文文。新闻》开售了!
只妖怪排队购买《文文。新闻》,将她们依次编号 ,每一只妖怪会购买若干份。然而,她们购买《文文。新闻》并不是为了阅读,而是是为了送给所有编号是自己倍数的的妖怪一份(自己可以不留)。也就是说,对于 的每只妖怪,依次进行:当手上的《文文。新闻》数量足够时,不进行购买,直接赠送;而不够时便会先向文文购买至刚好足够,再进行赠送。
文文为了使收益最大化,为每只妖怪详细制定了价格方案。具体地,第 只妖怪在已有 份《文文。新闻》时再买一份花费的价钱是 ,其中 是两个从 开始的长为 的正整数序列。
现在文文需要一个合理的定价方案,她决定从 全为 时开始调整。具体地,有以下三种操作:
1 x
询问以当前的 数组, 时文文能有多少营业额,因为结果可能很大,你需要求出答案对 取模后的结果。2 x y
适当地调整 数组的值:令 ;3 x y
适当地调整 数组的值:令 。
:经查证,量词为『只』和『个』的情况均有出现,THBwiki 中『一只妖怪』的匹配量显著多于『一个妖怪』,于是本题中采用『只』,并不是出题人的种族歧视。
输入格式
第一行一个整数 表示操作的数量。
第 行,每行 或 个整数,表示题目中的一次操作。
输出格式
每行一个整数,表示每次询问的获利对 取模后的结果。
5
1 5
2 2 5
3 1 3
1 5
1 6
4
6
12
提示
样例解释
第一个询问中,,两个序列中所有的元素均为 。 号妖怪买了 份报纸,每份报纸的收益都是 ,其他的妖怪都没有买报纸,总收益为 。
第二个询问中,有 ,序列中其他元素均为 。 号妖怪买了 份报纸,其中第 份报纸的收益是 ,第 份到第 份报纸的收益都是 ,其他的妖怪都没有买报纸,总收益为 。
第三个询问中,有 ,序列中其他元素均为 。让我们具体来看看这次询问中的过程:
-
号妖怪需要送其他每个妖怪各一份报纸,但是她没有报纸。于是她需要买 份报纸。其中第一份报纸的收益是 ,第 份到第 份报纸的收益都是 。然后她给了其他每个妖怪各一份报纸。
-
号妖怪需要送 号妖怪和 号妖怪各一份报纸,她已经从 号妖怪手中获得了一份报纸。于是她还需要买 份报纸,这份报纸的收益是 。
-
号妖怪需要送 号妖怪一份报纸,她已经从 号妖怪手中获得了一份报纸,不需要再买报纸。
-
号妖怪到 号妖怪都不需要送出报纸,也不需要再买报纸。
总收益为 。
数据规模与约定
本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。
对于 的数据,,,。
对于不同的子任务,作如下约定:
子任务编号 | 特殊性质 | 子任务分值 |
---|---|---|
没有修改操作 | ||
第一种操作中的每个 都相等 | ||
无 |