首页 > 试题广场 >

通信

[编程题]通信
  • 热度指数:12 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 783M,其他语言1566M
  • 算法知识视频讲解
有N个信号塔,第i个塔的位置是i,信号强度X_i(X_i保证互不相同)。 有N个人,第i个人的位置是i,一个人往左走一格要A秒,往右走一格要B秒。 这些人之间要传递信息,具体地,如果i有信息,那么i会依次做以下操作:
- 选择一个j满足1 ≤ j ≤ i,并找到一个k使得j ≤ k ≤ i并且X_k最大来保证通信。
- i, j同时向k移动,先到的会等另一个人直到两个人都到达。
- 等到i,j都到达k时,信息的传递瞬间完成,并且i,j瞬间回到原来的位置。
- 之后i会失去信息,j会获得信息。
请对每个i计算,如果初始i有信息,那么最少多少时间以后信息可以传递到1,并输出最少时间的方案数,方案数对2^32取模。 一个方案可以被描述成P_1=i,P_2,P_3,...,P_t=1,表示信息的传递是P_1->P_2->P_3-> ...->P_t。 两个方案被认为是不同的当且仅当t不同或者存在一个1 ≤ i ≤ t使得P_i不同。 特殊地,对于1,我们认为最少时间是0,方案数为1。

输入描述:
第一行三个数N,A,B。
接下来一行N个数表示X_i。
1 ≤ N ≤ 8*10^5,1 ≤ A,B ≤ 10^4


输出描述:
令f[i]表示从i出发的最小时间,g[i]表示最小时间的方案数。
输出两行,第一行f[1] xor f[2] xor f[3] xor ... xor f[n]
第二行g[1] xor g[2] xor g[3] xor g[4] xor ... xor g[n]。
f[n]请转成64位有符号整形(c++ long long)计算xor。
g[n]请转成32位无符号整形(c++ unsigned int)计算xor。
示例1

输入

6 13 3
2 4 3 5 6 1

输出

6
6

说明

(f[1] = 0 , g[1] = 1
f[2] = 3 , g[2] = 1
f[3] = 13, g[3] = 1
f[4] = 9 , g[4] = 2
f[5] = 12, g[5] = 4
f[6] = 13, g[6] = 1)