该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

某量子实验室记录了 $N$ 个量子比特在第 $1, 2, \dots, T$ 个时刻的状态。每个状态值为 $0$ 或 $1$。

对任意一个量子比特和任意一个时刻区间 $[L, R]$（$1 \leq L \leq R \leq T$），若该量子比特在区间内状态为 $1$ 的次数恰好为 $K$，则称该量子比特在该区间产生了一次有效叠加。

现在，请你统计：在所有量子比特、所有时刻区间中，有效叠加出现的总次数。

输入格式

第一行包含三个整数 $N, T, K$，分别表示量子比特数量、时刻数量、目标次数。

接下来 $N$ 行，每行包含 $T$ 个整数（$0$ 或 $1$），其中第 $i$ 行表示第 $i$ 个量子比特在各时刻的状态序列。

输出格式

输出一行，一个整数，表示有效叠加的总次数。

3 5 2
1 0 1 0 1
0 1 1 0 0
1 1 0 0 1

14

解释 #1

对于第 $1$ 个量子比特 $1\ 0\ 1\ 0\ 1$，满足条件的区间有：$[1,3]$、$[1,4]$、$[2,5]$、$[3,5]$。共 $4$ 个。

对于第 $2$ 个量子比特 $0\ 1\ 1\ 0\ 0$，满足条件的区间有：$[1,3]$、$[1,4]$、$[1,5]$、$[2,3]$、$[2,4]$、$[2,5]$。共 $6$ 个。

对于第 $3$ 个量子比特 $1\ 1\ 0\ 0\ 1$，满足条件的区间有：$[1,2]$、$[1,3]$、$[1,4]$、$[2,5]$。共 $4$ 个。

因此总次数为 $4 + 6 + 4 = 14$。

2 4 1
1 0 0 1
0 0 0 0

6

解释 #2

对于第 $1$ 个量子比特 $1\ 0\ 0\ 1$，恰好包含 $1$ 个状态为 $1$ 的区间有：$[1,1]$、$[1,2]$、$[1,3]$、$[2,4]$、$[3,4]$、$[4,4]$。共 $6$ 个。

对于第 $2$ 个量子比特 $0\ 0\ 0\ 0$，任意区间内都没有状态为 $1$，因此不存在恰好包含 $1$ 个状态为 $1$ 的区间。

所以答案为 $6 + 0 = 6$。

1 6 3
1 1 0 1 1 0

3

解释 #3

唯一的量子比特为 $1\ 1\ 0\ 1\ 1\ 0$。

恰好包含 $3$ 个状态为 $1$ 的区间有：$[1,4]$、$[2,5]$、$[2,6]$。共 $3$ 个。

1 3 0
0 0 0

6

解释 #4

唯一的量子比特在所有时刻的状态都为 $0$。

当 $K = 0$ 时，需要统计区间内恰好有 $0$ 个状态为 $1$ 的情况，也就是区间内所有值都为 $0$ 的区间。

当 $T = 3$ 时，一共有 $\frac{3 \times 4}{2} = 6$ 个区间，且它们全部满足条件，因此答案为 $6$。

数据范围

• 对于 $30\%$ 的评测用例，$N \leq 10$，$T \leq 100$；
• 对于 $60\%$ 的评测用例，$N \leq 50$，$T \leq 500$；
• 对于所有评测用例，$1 \leq N \leq 200$，$1 \leq T \leq 1000$，$0 \leq K \leq T$；保证输入中的所有状态值均为 $0$ 或 $1$。