PIPIOJ

Problem1531--玩弹簧的PIPI

1531: 玩弹簧的PIPI

Time Limit: 2 Sec Memory Limit: 256 MB
Submit: 22 Solved: 8
[Submit] [Status] [Web Board] [Creator:]

Description

$n$ 个弹簧围成一圈，编号为 $0,1,...,n-1$ ，第 $i$ 个弹簧的弹力为 $a_i$ ，当 $PIPI$ 站在第 $i$ 个弹簧时， $PIPI$ 可以被弹到 $[i-a_i,i+a_i]$ 的任意一个位置（注意位置 $0$ 与位置 $n-1$ 相邻，即可以把位置 $-1,-2,...$ 看作位置 $n-1,n-2,...$ ，位置 $n,n+1,...$ 看作位置 $0,1,...$ ）

$PIPI$ 现在站在位置 $s$ ，请问 $PIPI$ 至少需要被弹几次才能到达位置 $t$ ？如果不能到达输出 $-1$

Input

第一行 $3$ 个整数 $n,s,t(1\le n\le 10^7,0\le s,t<n)$
第二行 $4$ 个整数 $a_0,g,seed,p(0\le a_0,g,seed<p,1\le p\le n)$
对于 $1\le i<n$ ， $a_i=(a_{i-1}*g+seed)\bmod p$

Output

输出一行一个整数表示答案。

Sample Input

9 0 2 
1 3 4 7

Sample Output

HINT

经过递推计算后 $a_0,a_1,...,a_8$ 为 $1,0,4,2,3,6,1,0,4$

一开始 $PIPI$ 站在位置 $0$ ，由于 $a_0=1$ ，故 $PIPI$ 可以被弹到位置 $8,0,1$ 。
如果 $PIPI$ 被弹到位置 $1$ ，由于 $a_1=0$ ， $PIPI$ 就不能再移动了。
如果 $PIPI$ 被弹到位置 $8$ ，由于 $a_8=4$ ，故 $PIPI$ 可以被弹到位置 $4,5,6,7,8,0,1,2,3$ ， $PIPI$ 接下来直接被弹到位置 $2$ 即可。
因此最少需要被弹 $2$ 次。

Source/Category

困难

[Submit] [Status]