分数: 700 点
问题陈述
给定的是一系列 N 数字 a_1a_2\ldots a_N,其中每个元素是 1, 2,或 3。 让 x_{i,j} 定义如下:
- x_{1,j} := a_j \quad (1 \leq j \leq N)
- x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N 和 1 \leq j \leq N+1-i)
查找 x_{N,1}.
约束
- 2 \leq N \leq 10^6
- a_i = 1,2,3 (1 \leq i \leq N)
输入
输入由标准输入按以下格式给出:
N a_1a_2\ldotsa_N
输出
打印 x_{N,1}.
示例输入 1
4 1231
示例输出 1
1
x_{1,1},x_{1,2},x_{1,3},x_{1,4} 分别是 1,2,3,1.
x_{2,1},x_{2,2},x_{2,3} 分别是 |1-2| = 1,|2-3| = 1,|3-1| = 2.
x_{3,1},x_{3,2} 分别是 |1-1| = 0,|1-2| = 1.
最后, x_{4,1} = |0-1| = 1,所以答案是 1.
示例输入 2
10 2311312312
示例输出 2
0