B. 按位或

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

本题的评测时间较长,若发现有恶意利用此题堵塞评测队列的,我们会采取包括但不限于禁赛等措施

在神秘的信息加密领域,存在着一种古老而强大的加密方式。所有的信息被编码成一个庞大的数字数组 ,这些数字就像是守护信息宝藏的卫士。如今,密码学家们发现了一个关键线索 —— 一个神秘的数字 。在这个数组中,存在着一些连续的子数组,当对这些子数组中的所有数字进行按位或运算时,会得到一些不同的结果。只有找出这些按位或结果不同且小于 k 的个数,才有可能破解加密信息,揭开隐藏在背后的巨大秘密。而你,是被寄予厚望的解密高手,准备迎接这个挑战吧。

给定一个整数数组 ,从中找出所有连续的子数组,对每个子数组内的所有元素进行按位或运算,要求这些按位或运算得到的值 都不同且小于给定的整数 ,最后计算出满足条件的 个数。

输入格式

第一行输入一个整数 (1 ) 和 (1 ),表示数组 的长度和按位或运算结果的阈值。

第二行输入 个整数,每个整数 满足 1 ,表示数组 的元素。

输出格式

输出一个整数,表示满足条件的 的个数。

样例

输入 #1

2 2
1 1

输出 #1

1

输入 #2

3 8
1 2 4

输出 #2

6

输入 #3

3 8
2 6 7

输出 #3

3

输入 #4

3 4
2 6 7

输出 #4

1

输入 #5

4 13
4 2 3 10

输出 #5

7

数据范围与提示

以下[]中都表示某一连续子数组按位或得到的结果:

样例1:

[1],小于2的有1个
样例2:

[1],[2],[4],[3],[6],[7],小于8的有6个

样例3:

[2],[6],[7],小于8的有3个
样例4:

[2],[6],[7],总共有3个,小于4的有1个
样例5:

[2],[3],[4],[6],[7],[10],[11],[14],总共有8个,小于13的有7个