蓝桥杯2026年第十七届省赛真题-量子态叠加计数器

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

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

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

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

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

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

【样例说明 1】

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

、[3, 5] 。共 4 个。

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

、[2, 3] 、[2, 4] 、[2, 5] 。共 6 个。

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

、[2, 5] 。共 4 个。

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

【样例输入 2】

2 4 1

1 0 0 1

0 0 0 0

【样例输出 2】

6

【样例说明 2】

对于第 1 个量子比特 10 0 1，恰好包含 1 个状态为 1 的区间有：[1, 1] 、

[1, 2] 、[1, 3] 、[2, 4] 、[3, 4] 、[4, 4] 。共 6 个。

对于第 2 个量子比特 00 0 0，任意区间内都没有状态为 1，因此不存在

恰好包含 1 个状态为 1 的区间。

所以答案为 6+ 0 = 6。

【样例输入 3】

1 6 3

11 0 1 1 0

【样例输出 3】

3

【样例说明 3】

唯一的量子比特为 11 0 1 1 0。

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

【样例输入 4】

1 3 0

0 0 0

【样例输出 4】

6

【样例说明 4】

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

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

所有值都为 0 的区间。

当 T =3 时，一共有 3×24 =6 个区间，且它们全部满足条件，因此答案为

6。

【评测用例规模与约定】

对于 30% 的评测用例，N ≤ 10，T ≤ 100；

对于 60% 的评测用例，N ≤ 50，T ≤ 500；

对于所有评测用例，1 ≤ N ≤ 200，1 ≤ T ≤ 1000，0 ≤ K ≤ T；保证输入中

的所有状态值均为 0 或 1