#P1051. [BPOJ-R1D]War
[BPOJ-R1D]War
题目描述
在一款战争游戏中,一些玩家自立为王,建立了王国,而每一个王国都是紧挨着的,它们都有各自的编号,从 到 ,只有编号相邻的国家才能打仗,他们之间打仗必定会有一个国家灭亡,此时的各个国家的编号按从小到大重新赋予新的编号,比如原先各个国家的编号分别为: ,重排后变为 ,即原先的 变为 ,原先的 变为 ,原先的 变为 ,原先的 变为 ,原先的 变为 ,每一次变化后国家与国家编号的大小关系不变,且编号为由 开始的连续自然数,每打完一次仗就重排一次编号,一次只能打一场仗,所以上面的例子是不存在的。
战争规则是这样的: 双方猜拳确定胜负,胜利的国家威力变为两个国家之积,失败的国家灭亡。
打完仗后,获胜的国家会被复制,复制出来的国家会与某神秘国度(初始威力为 )打仗,如果复制的国家赢了,则它回取代神秘国度,成为新的神秘国度,与下一次复制出来的国家打仗。
现在,只有原始编号为 会打仗,请问这些国家打完仗后的神秘国度的威力最大为多少?
输入格式
第一行一个整数 。
接下来 个整数,第 个整数表示原使编号为 的国家士兵融合前的威力 。
接下来一个整数 。
接下来 行,每行两个整数 。
输出格式
共 行,每行一个整数,表示剩下的国家最大威力是多少,由于答案可能很大,你只需要输出答案对 取模的结果即可。
5
1 2 3 4 5
3
1 3
3 5
5 5
36
1200
1
提示
对于 的数据,满足 ,, 。
对于 的数据,满足 ,, 。
【#样例解释】
以下解释使用原编号,隐藏胜利国家的复制品与神秘国家打仗的环节。
对于第一组询问,先让 和 打仗,获胜国家威力为 ,神秘国度威力变为 ,再让 和胜利国家打仗,此时获胜国家威力为 ,神秘国度威力变为 。此时神秘国度威力为 ,可以证明不能再强了。
对于第二组询问,先让 和 打仗,再让 打仗,此时神秘国度威力为 ,可以证明不能再强了。
对于第三组询问,只有 一个国家,不打仗,神秘国度也不打仗,所以为 。
来源
题目来自 BPOJ Round1。
相关
在下列比赛中: