会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（拼多多机考题库），可解锁完整内容。

购买题库开通会员

设 $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'}$ 子矩形个数为

\sum_{r \cdot c = k} f_A(r) \cdot f_B(c).

题目内容

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

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

请从“运行结果”或“历史提交”选择一条记录

选择提交后开始分析

#P3535. 第3题-多多爱矩形