2242C.md (3159B)
1 Source: https://codeforces.com/problemset/problem/2242/C 2 3 C. Unstable Elements 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a sorted array of integers $[a_1, a_2, \dots, a_n]$. We can perform any number of operations of the following type on this array: 22 23 * mark the first element of the array, as well as all elements that are not equal to their left neighbors (that is, all elements $i$ such that $a_i \ne a_{i-1}$). 24 * then either delete all marked elements or duplicate them (that is, replace each marked element with two identical elements). 25 26 For example, consider the array $[\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}]$ (marked elements are shown in bold). If we delete all marked elements, we get $[1, 1, 4]$, and if we duplicate them, we get $[1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5]$. 27 28 The operations cannot be performed if the array becomes empty. After each operation, every element gets unmarked. 29 30 We call an array of integers $b$ reachable if it can be obtained from array $a$ by some number of the described operations. Your task is to count the number of reachable arrays of length $k$. 31 32 Input 33 34 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 35 36 Each test case consists of two lines: 37 38 * the first line contains two integers $n$ and $k$ ($1 \le n, k \le 3 \cdot 10^5$); 39 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 \le a_2 \le \dots \le a_n \le n$). Note that the array is sorted. 40 41 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$. 42 43 Output 44 45 For each test case, output one integer — the number of reachable arrays $b$ of length $k$. It can be shown that, under the constraints of the problem, the answer fits into a standard $32$-bit integer type. 46 47 Example 48 49 Input 50 51 ``` 52 10 53 54 1 5 55 56 1 57 58 4 5 59 60 1 1 2 2 61 62 3 1 63 64 1 1 1 65 66 4 8 67 68 1 2 3 4 69 70 8 6 71 72 1 1 1 2 2 2 2 2 73 74 6 3 75 76 1 1 2 2 3 3 77 78 10 7 79 80 1 1 1 2 2 3 3 3 3 4 81 82 12 5 83 84 1 1 1 1 2 2 2 3 3 4 4 4 85 86 6 5 87 88 1 1 2 2 3 3 89 90 3 1 91 92 1 2 2 93 ``` 94 95 Output 96 97 ``` 98 1 99 100 0 101 102 1 103 104 1 105 106 2 107 108 1 109 110 2 111 112 1 113 114 0 115 116 1 117 ``` 118 119 Note 120 121 In the first example, the following sequence of operations can be performed: 122 123 * $[\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1]$. 124 125 In the second example, it is impossible to obtain an array of length $5$. 126 127 In the third example, the following sequence of operations can be performed: 128 129 * $[\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1]$. 130 131 In the fifth example, the arrays $[1, 1, 2, 2, 2, 2]$ and $[2, 2, 2, 2, 2, 2]$ can be obtained: 132 133 * $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2]$; 134 * $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2]$. 135 136 In the seventh example, the arrays $[1, 1, 1, 3, 3, 3, 3]$ and $[3, 3, 3, 3, 3, 3, 3]$ can be obtained.