
ZOJ Problem Set  3942
A nonempty string S is called binary, if it consists only of characters "0" and "1". A substring S[l...r] (1 ≤ l ≤ r ≤ S) of string S = S_{1}S_{2}...S_{S} (where S is the length of string S) is string S_{l}S_{l + 1}...S_{r}. Peter has got a long binary string S starting with "0", and he wants to know the number of distinct nonempty substrings of the string S that the occurrences of "0" in the substring is exact M, where M is Peter's lucky number. Two substrings S[x...y] and S[p...q] are considered distinct if their content is different, i.e. S[x...y] ≠ S[p...q]. Since the binary string is very long, we will compress it. The compression method is:
For example, the runs of a binary string 00101100011110111101001111111 is {00, 1, 0, 11, 000, 1111, 0, 1111, 0, 1, 00, 1111111}, so it will be compressed into {2, 1, 1, 2, 3, 4, 1, 4, 1, 1, 2, 7}. InputThere are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case: The first line contains two integers N and M (2 ≤ N ≤ 2000, 0 ≤ M ≤ 10^{9})  the number of runs and Peter's lucky number. The next line contains N integers: A_{1}, A_{2}, ..., A_{N} (1 ≤ A_{i} ≤ 10^{6}), indicating the length of the each run. OutputFor each test case, output an integer denoting the answer. Sample Input1 3 2 3 2 1 Sample Output4 HintThe original binary string is 000110, the four substrings are: 00, 001, 0011, 0110. Author: LIN, Xi Source: The 13th Zhejiang Provincial Collegiate Programming Contest 