思路

• 设 $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$ 的段的个数），则

其中 $S1_A(r) = \sum_{L \ge r} \text{cntA}[L]$，$S2_A(r) = \sum_{L \ge r} \text{cntA}[L] \cdot L$。二者用后缀和 $O(n)$ 预处理即可。$f_B(c)$ 同理。

• 遍历 $k$ 的所有约数对 $(r, c)$（即 $r \cdot c = k$），累加 $f_A(r) \cdot f_B(c)$；当 $r \ne c$ 时再加上 $f_A(c) \cdot f_B(r)$ 即可避免重复。

• 复杂度：预处理 $O(n + m)$，遍历约数 $O(\sqrt{k})$，总复杂度 $O(n + m + \sqrt{k})$。空间 $O(n + m)$。

C++

#include <bits/stdc++.h>
using namespace std;

// 读取并统计某字符串中连续 'a' 段长的频次，返回 cnt[L] = 长度为 L 的段的个数
static void buildCount(const string &s, vector<long long> &cnt) {
	// 统计连续 'a' 的段长
	long long run = 0;
	for (char ch : s) {
		if (ch == 'a') {
			++run;
		} else if (run > 0) {
			if (run < (long long)cnt.size()) cnt[(size_t)run] += 1;
			run = 0;
		}
	}
	if (run > 0 && run < (long long)cnt.size()) cnt[(size_t)run] += 1;
}

// 根据 cnt[L] 预处理后缀和：S1[i] = sum_{L>=i} cnt[L], S2[i] = sum_{L>=i} cnt[L]*L
static void buildSuffix(const vector<long long> &cnt, vector<long long> &S1, vector<long long> &S2) {
	int N = (int)cnt.size() - 1;
	for (int i = N; i >= 1; --i) {
		S1[i] = S1[i + 1] + cnt[i];
		S2[i] = S2[i + 1] + cnt[i] * i;
	}
}

// 查询 f(r) = sum_{L>=r} cnt[L]*(L - r + 1) = S2[r] - (r-1)*S1[r]
static inline long long getCount(const vector<long long> &S1, const vector<long long> &S2, long long r) {
	if (r <= 0) return 0;
	if (r >= (long long)S1.size()) return 0;
	return S2[(size_t)r] - (r - 1) * S1[(size_t)r];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	long long n, m, k;
	string A, B;
	if (!(cin >> n >> m >> k)) return 0;
	cin >> A >> B;

	// cntA[L], cntB[L] 记录长度为 L 的连续 'a' 段数量
	vector<long long> cntA((size_t)n + 2, 0), cntB((size_t)m + 2, 0);
	buildCount(A, cntA);
	buildCount(B, cntB);

	// 后缀和数组
	vector<long long> S1A((size_t)n + 3, 0), S2A((size_t)n + 3, 0);
	vector<long long> S1B((size_t)m + 3, 0), S2B((size_t)m + 3, 0);
	buildSuffix(cntA, S1A, S2A);
	buildSuffix(cntB, S1B, S2B);

	long long ans = 0;

	// 遍历 k 的约数
	for (long long d = 1; d * d <= k; ++d) {
		if (k % d == 0) {
			long long r = d;
			long long c = k / d;
			// 贡献 fA(r)*fB(c)
			long long fa_r = getCount(S1A, S2A, r);
			long long fb_c = getCount(S1B, S2B, c);
			ans += fa_r * fb_c;
			// 若 r != c，再加上对称项 fA(c)*fB(r)
			if (r != c) {
				long long fa_c = getCount(S1A, S2A, c);
				long long fb_r = getCount(S1B, S2B, r);
				ans += fa_c * fb_r;
			}
		}
	}

	cout << ans << '\n';
	return 0;
}

Python

import sys
from math import isqrt

# 读取输入（使用更快的读取方式）
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); k = int(data[2])
A = data[3].decode()
B = data[4].decode()

# 统计连续 'a' 段长的频次：cnt[L] = 长度为 L 的段的个数
def build_count(s, size):
	# size 预期为 n 或 m
	cnt = [0] * (size + 2)
	run = 0
	for ch in s:
		if ch == 'a':
			run += 1
		else:
			if run > 0:
				cnt[run] += 1
				run = 0
	if run > 0:
		cnt[run] += 1
	return cnt

# 根据 cnt 预处理后缀和 S1, S2
def build_suffix(cnt):
	N = len(cnt) - 2
	S1 = [0] * (N + 3)
	S2 = [0] * (N + 3)
	for i in range(N, 0, -1):
		S1[i] = S1[i + 1] + cnt[i]
		S2[i] = S2[i + 1] + cnt[i] * i
	return S1, S2

# 查询 f(r) = S2[r] - (r-1)*S1[r]
def get_count(S1, S2, r):
	if r <= 0 or r >= len(S1):
		return 0
	return S2[r] - (r - 1) * S1[r]

cntA = build_count(A, n)
cntB = build_count(B, m)
S1A, S2A = build_suffix(cntA)
S1B, S2B = build_suffix(cntB)

ans = 0
lim = isqrt(k)
for d in range(1, lim + 1):
	if k % d == 0:
		r, c = d, k // d
		ans += get_count(S1A, S2A, r) * get_count(S1B, S2B, c)
		if r != c:
			ans += get_count(S1A, S2A, c) * get_count(S1B, S2B, r)

print(ans)

Java

import java.io.*;
import java.util.*;

public class Main {
	// 快速输入
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		String next() throws IOException {
			StringBuilder sb = new StringBuilder();
			int c;
			while ((c = read()) <= 32) {
				if (c == -1) return null;
			}
			while (c > 32) {
				sb.append((char)c);
				c = read();
			}
			return sb.toString();
		}
	}

	// 统计连续 'a' 段长的频次：cnt[L] = 长度为 L 的段的个数
	static long[] buildCount(String s, int size) {
		long[] cnt = new long[size + 2];
		int run = 0;
		for (int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);
			if (ch == 'a') {
				run++;
			} else {
				if (run > 0) {
					cnt[run] += 1;
					run = 0;
				}
			}
		}
		if (run > 0) cnt[run] += 1;
		return cnt;
	}

	// 根据 cnt 预处理后缀和 S1, S2
	static void buildSuffix(long[] cnt, long[] S1, long[] S2) {
		int N = cnt.length - 2;
		for (int i = N; i >= 1; --i) {
			S1[i] = S1[i + 1] + cnt[i];
			S2[i] = S2[i + 1] + cnt[i] * i;
		}
	}

	// 查询 f(r) = S2[r] - (r-1)*S1[r]
	static long getCount(long[] S1, long[] S2, long r) {
		if (r <= 0 || r >= S1.length) return 0L;
		return S2[(int)r] - (r - 1) * S1[(int)r];
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		long n = Long.parseLong(fs.next());
		long m = Long.parseLong(fs.next());
		long k = Long.parseLong(fs.next());
		String A = fs.next();
		String B = fs.next();

		long[] cntA = buildCount(A, (int)n);
		long[] cntB = buildCount(B, (int)m);

		long[] S1A = new long[(int)n + 3];
		long[] S2A = new long[(int)n + 3];
		long[] S1B = new long[(int)m + 3];
		long[] S2B = new long[(int)m + 3];

		buildSuffix(cntA, S1A, S2A);
		buildSuffix(cntB, S1B, S2B);

		long ans = 0L;
		long d = 1;
		while (d * d <= k) {
			if (k % d == 0) {
				long r = d, c = k / d;
				ans += getCount(S1A, S2A, r) * getCount(S1B, S2B, c);
				if (r != c) {
					ans += getCount(S1A, S2A, c) * getCount(S1B, S2B, r);
				}
			}
			d++;
		}
		System.out.println(ans);
	}
}

题目内容

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