题目描述
Dave 在研究一种数字矩阵时遇到了一个挑战。
给定一个由数字 0∼90∼9 构成的字符串 SS，其长度为 nn。他可以据此构造一个 n×nn×n 的矩阵，其中位于第 ii 行第 jj 列的元素值等于 SS 中第 ii 个字符与第 jj 个字符所对应数字的乘积。例如，若 SS 的第 33 位是 55，第 77 位是 22，则矩阵中 (3,7)(3,7) 位置（第三行第七列）的元素为 5×2=105×2=10。
现在，给定一个整数 TT，Dave 想知道这个矩阵中有多少个不同的子矩阵，其内部所有元素之和恰好等于 TT。
这里的子矩阵定义为由任意连续行和列围成的矩形区域（包括仅含单个元素的矩形）。请你帮助他解决这个问题。
输入格式
第一行一个整数 TT。
第二行一个字符串 SS。
输出格式
一行一个整数表示答案。
数据范围
对于 30%30% 的数据，∣S∣≤50∣S∣≤50。
对于 50%50% 的数据，∣S∣≤500∣S∣≤500。
对于 100%100% 的数据，0≤T≤1090≤T≤109，∣S∣≤4000∣S∣≤4000。
样例数据
输入:
5
123
输出:
2
说明:
A矩阵为：
1 2 3
2 4 6
3 6 9
符合题意的子矩阵为 [(2,1),(3,1)] 与 [(1,2),(1,3)]（用矩阵的左上角和右下角坐标表示矩阵）。
详见代码：
#include <bits/stdc++.h>
using namespace std;
long long countSubmatrices(int T, const string& S)
{
int n = S.length();
vector<int> nums(n);
for (int i = 0; i < n; i++)
{
nums[i] = S[i] - '0';
}
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++)
{
prefix[i + 1] = prefix[i] + nums[i];
}
unordered_map<int, int> rowSumCount;
for (int r1 = 0; r1 < n; r1++)
{
for (int r2 = r1; r2 < n; r2++)
{
int rowSum = prefix[r2 + 1] - prefix[r1];
rowSumCount[rowSum]++;
}
}
long long result = 0;
for (int c1 = 0; c1 < n; c1++)
{
for (int c2 = c1; c2 < n; c2++)
{
int colSum = prefix[c2 + 1] - prefix[c1];
if (colSum == 0)
{
if (T == 0)
{
result += n * (n + 1) / 2;
}
}
else
{
if (T % colSum == 0)
{
int targetRowSum = T / colSum;
if (rowSumCount.count(targetRowSum))
{
result += rowSumCount[targetRowSum];
}
}
}
}
}
return result;
}
int main()
{
int T;
string S;
cin >> T >> S;
cout << countSubmatrices(T, S) << endl;
return 0;
}