二进制数组

题目描述

给定一个正整数数组构造二进制数 n，计算 (n XOR (n >> 1)) % m。其中二进制数的构造规则为：数组中第 i 个元素表示连续 a_i 个 i%2 的二进制位（从高位到低位排列）。

算法思路

核心观察

1. 异或特性：n XOR (n >> 1) 的二进制中，只有相邻位不同的位置会产生1

题目内容

对于给定的正偶数$n$和正整数$m$，求解下式:

​ $n\ xor$$\frac{n}{2}$$mod\ m$

这显然难不倒你，所以，我们将会使用一种特殊的方式给出$n$的二进制形式：给出一个由$k$个整数构成的数组{$a_1,a_2,...,a_k$}，其中，第$i$个整数$a_i$代表$n$的二进制表示中，从高位到低位，恰好有连续$a_i$个$a_i\ mod \ 2$。更具体地，如果数组$a$={$3,4, 1, 2$}，那么，第一个整数$a_1$就代表有$3$ 个$3\ mod\ 2=1$,第二个整数$a_2$就代表有$4$ 个$4\ mod \ 2=0$，$......$。最终，可以得到$n$的二进制表示为$1110000100$。

输入描述

第一行输入两个整数 $k,m(1≦k≦2×10^5;1≦m≦10^9)$。

第二行输入$k$个正整数$a_1,a_2,...,a_k(1≦a_i≦10^9)$。

除此之外，保证单个测试文件的$a_i$之和不超过$10^9$。

输出描述

输出一个十进制整数，代表式子的最终答案.

样例1

输入

4 15
3 4 1 2

输出

12