思路

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

题目内容

给定两个仅包含小写字符 $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$ ?

输入描述

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

第二行为字符串 $A$

第三行为字符串 $B$

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

输出描述

一个整数 $k$

样例1

输入

3 3 2
aaa
aba

输出

4

说明

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

$aba$

$aba$

$aba$

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

样例2

输入

3 6 4
aaa
aaaaaa

输出

19