P16269 [Lanqiao Cup 2026 NOI Qualifier Java B Group] Quantum State Superposition Counter

A quantum laboratory recorded the states of $N$ qubits at times $1, 2, \dots, T$. Each state value is $0$ or $1$. For any qubit and any time interval $[L, R]$ ($1 \leq L \leq R \leq T$), if the number of times the qubit’s state is $1$ within the interval is exactly $K$, then we say the qubit produces one valid superposition in this interval. Now, please count: among all qubits and all time intervals, the total number of valid superpositions.

The first line contains three integers $N, T, K$, representing the number of qubits, the number of time points, and the target count. The next $N$ lines each contain $T$ integers ($0$ or $1$). The $i$-th line represents the state sequence of the $i$-th qubit over all time points.

Output one line with one integer, indicating the total number of valid superpositions.

### Sample Explanation 1 For the 1st qubit $1\ 0\ 1\ 0\ 1$, the intervals that satisfy the condition are: $[1,3]$, $[1,4]$, $[2,5]$, $[3,5]$. There are $4$ intervals in total. For the 2nd qubit $0\ 1\ 1\ 0\ 0$, the intervals that satisfy the condition are: $[1,3]$, $[1,4]$, $[1,5]$, $[2,3]$, $[2,4]$, $[2,5]$. There are $6$ intervals in total. For the 3rd qubit $1\ 1\ 0\ 0\ 1$, the intervals that satisfy the condition are: $[1,2]$, $[1,3]$, $[1,4]$, $[2,5]$. There are $4$ intervals in total. Therefore, the total count is $4 + 6 + 4 = 14$. ### Sample Explanation 2 For the 1st qubit $1\ 0\ 0\ 1$, the intervals that contain exactly $1$ state equal to $1$ are: $[1,1]$, $[1,2]$, $[1,3]$, $[2,4]$, $[3,4]$, $[4,4]$. There are $6$ intervals in total. For the 2nd qubit $0\ 0\ 0\ 0$, there is no state equal to $1$ in any interval, so there are no intervals that contain exactly $1$ state equal to $1$. So the answer is $6 + 0 = 6$. ### Sample Explanation 3 The only qubit is $1\ 1\ 0\ 1\ 1\ 0$. The intervals that contain exactly $3$ states equal to $1$ are: $[1,4]$, $[2,5]$, $[2,6]$. There are $3$ intervals in total. ### Sample Explanation 4 The only qubit has state $0$ at all time points. When $K = 0$, we need to count the cases where there are exactly $0$ states equal to $1$ in the interval, i.e., intervals where all values are $0$. When $T = 3$, there are $\frac{3 \times 4}{2} = 6$ intervals in total, and all of them satisfy the condition, so the answer is $6$. ### Constraints For $30\%$ of the testdata, $N \leq 10$, $T \leq 100$. For $60\%$ of the testdata, $N \leq 50$, $T \leq 500$. For all testdata, $1 \leq N \leq 200$, $1 \leq T \leq 1000$, $0 \leq K \leq T$. It is guaranteed that all state values in the input are either $0$ or $1$. Translated by ChatGPT 5