思路

• 设 $A$ 和 $B$ 的 $\text{'a'}$ 视作 $1$，否则为 $0$。则 $C_{ij} = 1$ 当且仅当 $A_i = 1$ 且 $B_j = 1$。这使得所有仅含 $\text{'a'}$ 的子矩形等价于：选择一段只由 $A$ 中的 $1$ 组成的连续行、以及一段只由 $B$ 中的 $1$ 组成的连续列。
• 记 $f_A(r)$ 为 $A$ 中仅由 $\text{'a'}$ 构成、长度恰为 $r$ 的连续子段数量；$f_B(c)$ 类似。则面积为 $k$ 的全 $\text{'a'}$ 子矩形个数为

• 快速计算 $f_A(r)$：设 $A$ 中连续 $\text{'a'}$ 的段长频次为 $\text{cntA}[L]$（长度为 $L$ 的段的个数），则

题目内容

给定两个仅包含小写字符 $a$ 和 $b$ 的字符串 $A$ 和 $B$ ，长度分别为 $n$ 和 $m$ ，现在根据 $A$ 和 $B$ 构造一个 $n*m$ 的字符矩阵 $C$ ，其中 $C_{ij}$ 的值由 $A_i$ 和 $B_j$ 决定，具体计算方式如下:

• 如果 $A_i$ 和 $B_j$ 都为 $a$ ，则 $C_{ij}$ 为 $a$ ;

• 否则 $C_{ij}$ 为 $b$ 。

多多对字符 $a$ 情有独钟，他想知道矩阵 $C$ 中共有多少个仅包含 $a$ 的子矩形，并且其字符总数恰好为 $k$ ?