题目描述
有 N 个信号塔,第 i 个塔的位置是 i,信号强度 Xi(Xi 保证互不相同)。
有 N 个人,第 i 个人的位置是 i,一个人往左走一格要 A 秒,往右走一格要 B 秒。
这些人之间要传递信息,具体地,如果 i 有信息,那么 i 会依次做以下操作:
- 选择一个 j 满足 1≤j≤i,并找到一个 k 使得 j≤k≤i 并且 Xk 最大来保证通信。
- i,j 同时向 k 移动,先到的会等另一个人直到两个人都到达。
- 等到 i,j 都到达 k 时,信息的传递瞬间完成,并且 i,j 瞬间回到原来的位置。
- 之后** i 会失去信息**,j 会获得信息。
请对每个 i 计算,如果初始 i 有信息,那么最少多少时间以后信息可以传递到 1,并输出最少时间的方案数,方案数对 232 取模。
一个方案可以被描述成 P1=i,P2,P3,…,Pt=1,表示信息的传递是 P1→P2→P3→⋯→Pt。
两个方案被认为是不同的当且仅当 t 不同或者存在一个 1≤i≤t 使得 Pi 不同。
特殊地,对于 1,我们认为最少时间是 0,方案数为 1。
输入格式
第一行三个数 N,A,B。
接下来一行 N 个数表示 Xi。
输出格式
令 fi 表示从 i 出发的最小时间,gi 表示最小时间的方案数。
输出两行,第一行 f1⊕f2⊕f3⊕⋯⊕fn。
第二行 g1⊕g2⊕g3⊕g4⊕⋯⊕gn。
fn 请转成 **64 位有符号整形(C++ long long
)**计算 ⊕。
gn 请转成 **32 位无符号整形(C++ unsigned int
)**计算 ⊕。
样例
6 13 3
2 4 3 5 6 1
6
6
⎩⎨⎧f1=0f2=3f3=13f4=9f5=12f6=13g1=1g2=1g3=1g4=2g5=4g6=1
数据范围与提示
1≤N≤8×105,1≤A,B≤104