题目背景

2023第一届粤港澳信息学创新大赛初中组复赛T1

注意：本题是以文件读写的方式进行评测，请在代码中使用freopen()等文件读写的方式进行输入输出。

文件名请参考本标题下方的“文件IO:”后面的内容

题目描述

卤蛋对撞是鸭嘴兽们最喜欢的游戏。

具体来说，鸭嘴兽会把$n$ 个卤蛋放成一排，每个卤蛋会有一个美味值$a_i (1 \le i \le n)$， 表示这个卤蛋是否卤得入味。$n$个卤蛋排成一排后，裁判会给出一个目标美味值$k$。鸭嘴兽可以选择一个长度大于$1$ 的区间$[L,R]$，轻轻拨一下第$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 a_R)$， 如果其值为$k$， 则鸭嘴兽可以获得游戏的胜利。

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

输入格式

第一行是一个整数$n$， 表示卤蛋的个数。

第二行是$n$ 个正整数，第$i$ 个数表示第$i$ 个卤蛋的美味值$a_i$ 。

第三行是一个正整数$k$， 表示目标美味值。

输出格式

一行，一个整数，表示答案。

3
8 4 2
2

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$ 。

30
2 2 1 1 4 4 4 4 1 2 3 4 1 1 2 2 1 3 2 2 3 4 4 4 4 4 2 1 3 4
2

8