上海市计算机学会竞赛平台2025年2月月赛丙组子矩阵和

题目描述

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;
}