Zeratul有一个长度为nn的字符串，字符串只包含0和1两种字符。 现在他想知道，这个字符串中有多少非空子串满足“0和1两种字符的个数相等”。

假设字符串为s，长度为n。我们可以用一个变量cnt来记录当前为止0出现的次数减去1出现的次数的值。如果s的前i个字符的cnt值等于s的前j个字符的cnt值，那么s的第j+1到第i个字符组成的子串就符合条件。

具体地，我们可以使用一个哈希表来记录每个cnt值第一次出现的位置。对于当前处理到的位置i，我们在哈希表中查找cnt值为当前值减去0出现次数与1出现次数差值的位置，如果存在这样的位置j，那么s[j+1:i]就是一个合法的子串。我们统计所有符合条件的子串个数即可。

时间复杂度：O(n)。

代码如下：

相关问题

Zeratul有一个长度为n的字符串，字符串只包含0和1两种字符。 现在他想知道，这个字符串中有多少非空子串满足“0和1两种字符的个数相等”。

算法1：

暴力枚举

对于每个子串都判断一遍是否满足条件，时间复杂度O(n^3)。

算法2：

前缀和

对于每一个位置i，维护一个前缀和p[i]表示从1~i中0的个数减去1的个数。如果有一个子串s[l,r]满足0和1的个数相等，那么有p[r]-p[l-1]=0。因此我们可以枚举左右端点，然后计算前缀和之差是否为0。时间复杂度O(n^2)。

算法3：

哈希

我们可以将0视为-1，将1视为1，那么0和1个数相等的子串就是和为0的子串。因此我们可以维护一个前缀和q[i]表示从1~i的和，然后对于每个位置i，我们在之前出现过的所有位置中查找是否有一个位置j，使得q[i]-q[j]=0，如果有，那么i和j之间的子串就是一个满足条件的子串。我们可以用哈希表来维护之前出现过的每个前缀和所对应的位置。时间复杂度O(n)。

C++ 代码

对称性和连通性看上去是没什么关系的问题，但是Zeratul为了强行出一道暴力题，想出了这样一个问题： 一个 n × n n×n的01矩阵，有多少种情况使得它满足： 这个01矩阵具有中心对称性，即旋转180度后不变。 这个矩阵不存在0，或者所有的0都在同一个四连块里。

这是一个有趣的问题！为了解决这个问题，我们可以考虑使用组合数学的方法。首先，我们来看中心对称性的情况。

对于一个 n × n 的矩阵来说，如果它具有中心对称性，那么对于每一个位置 (i, j)，都需要找到一个位置 (n-i+1, n-j+1)，使得它们的值相等。由于这个矩阵只包含 0 和 1，我们可以分两种情况讨论：

1. 如果 (i, j) 和 (n-i+1, n-j+1) 的值都为 0，那么这两个位置可以是任意位置，所以有 2^(n^2/4) 种可能性。
2. 如果 (i, j) 和 (n-i+1, n-j+1) 的值都为 1，那么这两个位置也可以是任意位置，所以有 2^(n^2/4) 种可能性。

因此，对于中心对称性的情况，总共有 2^(n^2/4) × 2^(n^2/4) = 2^(n^2/2) 种可能性。

接下来，我们来看不存在 0 或所有的 0 在同一个四连块里的情况。

如果不存在 0，那么所有的位置都必须是 1，所以只有一种可能性。

如果所有的 0 都在同一个四连块里，那么这个四连块可以是任意大小的矩形，从 1 × 1 到 (n-1) × (n-1)。对于一个 k × k 的矩形来说，有 (n-k+1)^2 种可能性。所以，对于所有可能的 k，总共有 ∑[(n-k+1)^2] 种可能性。

综上所述，满足条件的矩阵总共有 2^(n^2/2) + 1 + ∑[(n-k+1)^2] 种可能性。