设 $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).

P3535.第3题-多多爱矩形

1000ms

Difficulty: 8

所属公司 : 拼多多

算法与标签>数学

题目内容

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

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

三行，第一行三个正整数 $n,m,k$ ，分别表示字符串 $A$ 和 $B$ 的长度，以及多多想知道的子矩形个数。

第二行为字符串 $A$

第三行为字符串 $B$

$(1<= n,m <= 1000,000,1 <= k<= n*m)$

一个整数 $k$

输入

3 3 2
aaa
aba

输出

说明

由 $A$ 和 $B$ 构成的矩形 $C$ 为

$aba$

所以有四个子矩形全都为 $a$

输入

3 6 4
aaa
aaaaaa

输出

输入

预期输出（选填）