U537931 卤蛋对撞(eggs)

题目描述

《卤蛋对撞》游戏规则

《卤蛋对撞》是鸭嘴兽们最喜欢的游戏。具体规则如下：

• 鸭嘴兽会把$n$个卤蛋排成一排，每个卤蛋有一个美味值$a_i(1 \leq i \leq n)$，表示这个卤蛋是否卤得入味。
• $n$个卤蛋排成一排后，裁判会给出一个目标美味值$k$。
• 鸭嘴兽可以选择一个长度大于1的区间$[L,R](1 \leq L < R \leq n)$，轻轻拨一下第$L$个卤蛋，卤蛋会向右倒下撞到第$L + 1$个卤蛋，然后第$L + 1$个卤蛋又会向右倒下撞到第$L + 2$个卤蛋，以此类推，直到第$R - 1$个卤蛋撞到第$R$个卤蛋，鸭嘴兽会避免下一次碰撞的发生。
• 每个卤蛋的调味料都不一样，对撞会影响美味值。当第$i$个卤蛋撞击第$i + 1$个卤蛋后，第$i + 1$个卤蛋的美味值$a_{i+1}$会变成$a_i \oplus a_{i+1}$，其中$a_i \oplus a_{i+1}$表示$\lfloor\frac{a_i}{a_{i+1}}\rfloor$，即下取整除法，如$7 \oplus 2 = \lfloor\frac{7}{2}\rfloor = 3$。
• 区间$[L,R]$的所有卤蛋完成对撞后，第$R$个卤蛋的美味值将变为$(((a_L \oplus a_{L+1}) \oplus a_{L+2}) \oplus \cdots) \oplus a_R$，如果其为$k$，则鸭嘴兽可以获得游戏的胜利。

现在鸭嘴兽们想知道，给定一排卤蛋和目标美味值，能获得游戏胜利的区间有多少个。

输入格式

输入格式说明：

• 第一行是一个整数$n$，表示卤蛋的个数。
• 第二行是$n$个正整数，第$i$个数表示第$i$个卤蛋的美味值$a_i$。
• 第三行是一个正整数$k$，表示目标美味值。

输出格式

一个整数，表示答案

输入输出样例 #1

输入 #1

3
8 4 2
2

输出 #1

2

说明/提示

样例1解释

选择区间$[1,2]$，第2个卤蛋的美味值是$8 \oplus 4 = \lfloor\frac{8}{4}\rfloor$，能获得游戏胜利。

选择区间$[1,3]$，第3个卤蛋的美味值是$(8 \oplus 4) \oplus 2 = 1$，不能获得游戏胜利。

选择区间$[2,3]$，第3个卤蛋的美味值是$4 \oplus 2 = 2$，能获得游戏胜利。

所以能获得游戏胜利的区间有2个。

数据范围

• 对于30%的数据，满足$n \leq 500, k \leq 500, a_i \leq 10^4$。
• 对于50%的数据，满足$n \leq 10^4, k \leq 10^4, a_i \leq 10^4$。
• 对于另外20%的数据，满足$a_i > 1$。
• 对于100%的数据，满足$n \leq 5 \times 10^5, k \leq 10^9, a_i \leq 10^9$。