Informatica Online Judge

  AND #2 [2249 / 08C9]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 15   Total Tried : 16


The Champion of this Problem (C++) : ajou709 - 50ms / 539byte
My Best Submission (C++) : N/A

[35th 이경렬]
Writer ID : [gs17076]

Background

길이 n의 수열이 있다. 각 항은 모두 자연수이다.

이 수열의 i번째 항부터 j번째 항까지의 합을 f(i, j)라 하자. (1<=i<=j<=n)

경렬이는 주어진 수 k에 대하여 f(i, j)가 정확히 k가 되는 순서쌍 (i, j)의 개수를 구하는 문제를 풀었다.

문제가 쉽게 풀려 재미없었던 경렬이는 새로운 함수 g(i, j)를 만들었다. (1<=i<=j<=n)

g(i, j)는 주어진 수열 {a_i}의 i번째 항부터 j번째 항까지 bitwise AND 연산한 값이다.

경렬이는 주어진 수 k에 대하여 g(i, j)가 정확히 k가 되는 순서쌍 (i, j)의 개수를 찾을 수 있을까?

Input

첫 줄에는 수열의 길이 n과 자연수 k가 입력된다.

두 번째 줄에는 a_1부터 a_n까지 n개의 자연수가 차례로 입력된다.

Sub-Task Info

#2: 1<=n<=2000000, 1<=k<=1000, 1<=a_i<=1000

Output

첫 줄에 g(i, j)가 k가 되는 순서쌍 (i, j)의 개수를 출력한다.
(1<=i<=j<=n)

IO Example

입력1
4 4
4 5 6 7

출력1
6

입력2
4 2
4 5 6 7

출력2
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]