#1514. 报社天狗
报社天狗
题目描述
新一期《文文。新闻》开售了!
只妖怪排队购买《文文。新闻》,将她们依次编号 ,每一只妖怪会购买若干份。然而,她们购买《文文。新闻》并不是为了阅读,而是是为了送给所有编号是自己倍数的的妖怪一份(自己可以不留)。也就是说,对于 的每只妖怪,依次进行:当手上的《文文。新闻》数量足够时,不进行购买,直接赠送;而不够时便会先向文文购买至刚好足够,再进行赠送。
文文为了使收益最大化,为每只妖怪详细制定了价格方案。具体地,第 只妖怪在已有 份《文文。新闻》时再买一份花费的价钱是 ,其中 是两个从 开始的长为 的正整数序列。
现在文文需要一个合理的定价方案,她决定从 全为 时开始调整。具体地,有以下三种操作:
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
题目来源:洛谷 P11772