TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3723
  • 题目
  • P3723宝批龙
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 时限1000ms
    问题描述

    【问题描述】

        宝批龙,又叫宝气。虽然恐龙已经灭绝数千万年,但是宝批龙却仍然顽强的活在这个世界上,而且经常发宝。

        从前有座山,山上有很多个黑曲麻恐的防空洞,每个黑曲麻恐的防空洞里都有若干个宝批龙,宝批龙都发同样的宝。

    从前有座山,这座山只有一个山顶。山上有很多条上山的路,每条路的终点都是山顶。

    山上有很多个黑曲麻恐的防空洞,其中山顶有一个黑曲麻恐的防空洞。除了山顶的黑曲麻恐的防空洞,山上的其他每一个黑曲麻恐的防空洞都可以向山顶的方向走,而且这个方向是唯一的。从一个黑曲麻恐的防空洞向着上山方向走一段距离之后,可以到达另外一个黑曲麻恐的防空洞,到达的这个黑曲麻恐的防空洞称为下面那个黑曲麻恐的防空洞的上洞。

    每个黑曲麻恐的防空洞里都有若干个宝批龙,每个黑曲麻恐的防空洞的容纳量是有限的,一个黑曲麻恐的防空洞里住的宝批龙数量不能太多,否则会非常拥挤。

    宝批龙都发同样的宝,他们认为每个黑曲麻恐的防空洞的上洞里住的宝批龙数量不能超过这个黑曲麻恐的防空洞里住的宝批龙数量,除非上洞恰好住满。如果违背了这个规则,就是发宝失败,他们不再是宝批龙,宝批龙就从此灭绝。

    现在你知道了每个黑曲麻恐的防空洞的容纳量,你想计算山上的宝批龙有多少种分布情况。

    输入格式

    第一行一个整数,表示黑曲麻恐的防空洞的数量。每个黑曲麻恐的防空洞按编号,其中编号为1的黑曲麻恐的防空洞在山顶。

    第二行个整数,第i个数,表示第i个黑曲麻恐的防空洞的容纳量,即这个黑曲麻恐的防空洞里住的宝批龙数量必须在范围之内。

    第三行个整数,第i个数是,表示第i+1个黑曲麻恐的防空洞的上洞的编号。

    输出格式

    一行一个整数,表示山上宝批龙分布情况数量mod 1234567891(这是 个素数)的结果。 

    样例输入 1


    2 3 3 
    1 1

    样例输出 1

    41

    样例输入 2


    3 1 3 
    1 1 

    样例输出 2

    19

    提示

    【样例解释1】

    如果第个黑曲麻恐的防空洞里住个宝批龙,第个黑曲麻恐的防空洞都可以或个宝批龙,共有6种方案。

    如果第个黑曲麻恐的防空洞里住个宝批龙,第个黑曲麻恐的防空洞都可以住或者个宝批龙,共种方案。

    如果第个黑曲麻恐的防空洞里住个宝批龙,第个黑曲麻恐的防空洞都可以住或个宝批龙,共种方案。

    累计总共种方案。

     

    【样例解释2】

    如果第个黑曲麻恐的防空洞里住个宝批龙,第个黑曲麻恐的防空洞可以住或个宝批龙,第个黑曲麻恐的防空洞可以住或个宝批龙,共有种方案。

    如果第个黑曲麻恐的防空洞里住个宝批龙,第个黑曲麻恐的防空洞可以住个宝批龙,第个黑曲麻恐的防空洞可以住或个宝批龙,共有种方案。

    如果第个黑曲麻恐的防空洞里住个宝批龙,第个黑曲麻恐的防空洞无论住多少个宝批龙都不行,共有种方案。

    如果第个黑曲麻恐的防空洞里住个宝批龙,第个黑曲麻恐的防空洞可以住或个宝批龙,第个黑曲麻恐的防空洞可以住或个宝批龙,共有种方案。

    累计总共种方案。


    【数据范围】
    对于20%的数据,1≤𝑛≤8,1≤𝑐𝑖≤10;

    对于另外10%的数据,所有𝑐𝑖=1; 对于另外10%的数据,所有𝑢𝑖=𝑖−1;

    对于另外20%的数据,1≤𝑛≤10^5,1≤𝑐𝑖≤10;

    对于100%的数据,1≤𝑛≤5×10^5,1≤𝑐𝑖≤100。 


    来源  nodgd造