在C ++中计算具有总和可分解为'k'的子矩阵
给定行xcol矩阵作为输入。目的是找到matrix[row][col]中的所有子矩阵，以使该子矩阵的元素之和可被整数k整除。
如果矩阵是mat[3][3]并且k是4，那么子矩阵将如下所示：-
让我们通过示例来理解。
例如
输入-矩阵[3][3]={{1,1,1}，{2,2,2}，{3,3,3}}k=4
输出-总和可分解为'k'的子矩阵的计数为：4
说明- 子矩阵将如上所示。
输入-矩阵[3][3]={{1,1,1}，{2,2,2}，{3,3,3}}k=12
输出-总和可分解为'k'的子矩阵的计数为：4
说明-子矩阵如下所示：-
以下程序中使用的方法如下
在这种方法中，我们将从左到右遍历矩阵，对于每对左右列，将子矩阵的元素添加到数组arr[]中，并分别计算其元素和具有被k整除的子数组的和。
函数check_val()将具有子矩阵元素的数组作为一维数组。现在计算累积总和，并用k检验余数，并将余数的频率存储在数组arr_2[]中。
以matrix[row][col]和整数k为输入。
函数check_val（intarr[]，intsize，intk）接受子矩阵元素的arr[]并返回arr中所有可被k整除的子数组的计数
将变量count和temp设为0。
取数组arr_2[]来存储k的累积和的余数的频率。
使用for循环从i=0到i<size计算累积总和。将每个arr[i]与temp相加，并使用arr_2[（（（temp％k）+k）％k]++来增加余数的频率（对于负和取mod两次）。
再次使用循环遍历频率数组arr_2[]并为每个值>1添加arr_2[i]*（arr_2[i]-1））/2来计算所有可能的子数组的数量。
最后添加arr_2[0]进行计数。
函数matrix_divisible（intmatrix[row][col]，intsize，intk）接受输入子矩阵，并返回所有可被k整除的子矩阵的计数。
将初始计数设为0。
取一个临时数组arr[size]。
使用两个for循环设置左列索引i和右列索引j。
计算元素之和为arr[temp]+=matrix[temp][j]。
对于arr[]中的子数组数，请添加check_val(arr,size,k)计数。
在所有for循环的末尾，返回count作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
#define row 10
#define col 10
int check_val(int arr[], int size, int k) {
int count = 0;
int temp = 0;
int arr_2[k];
memset(arr_2, 0, sizeof(arr_2));
for (int i = 0; i < size; i++) {
temp = temp + arr[i];
arr_2[((temp % k) + k) % k]++;
}
for (int i = 0; i < k; i++) {
if (arr_2[i] > 1) {
count += (arr_2[i] * (arr_2[i] - 1)) / 2;
}
}
count = count + arr_2[0];
return count;
}
int matrix_divisible(int matrix[row][col], int size, int k) {
int count = 0;
int arr[size];
for (int i = 0; i < size; i++) {
memset(arr, 0, sizeof(arr));
for (int j = i; j < size; j++) {
for (int temp = 0; temp < size; ++temp) {
arr[temp] += matrix[temp][j];
}
count = count + check_val(arr, size, k);
}
}
return count;
}
int main() {
int matrix[row][col] = {{2,4,-1},{6,1,-9},{2,2, 1}};
int size = 3, k = 4;
cout << "Count of sub-matrices having sum divisible ‘k’ are: " << matrix_divisible(matrix, size, k);
return 0;
}如果我们运行上面的代码，它将生成以下输出
输出结果
Count of sub-matrices having sum divisible 'k' are: 7