Đếm ma trận con có tổng chia hết cho k trong C++

Cho ma trận row x col đầu vào. Mục tiêu: tìm tất cả ma trận con trong matrix[row][col] sao cho tổng các phần tử của ma trận con chia hết cho số nguyên k.

Nếu ma trận mat[3][3] và k = 4 thì các ma trận con như hình minh họa.

Hiểu qua ví dụ

Ví dụ 1

Đầu vào: matrix[3][3] = {{1,1,1}, {2,2,2}, {3,3,3}}, k = 4

Đầu ra: Số ma trận con tổng chia hết cho k: 4

Giải thích: Các ma trận con như minh họa.

Ví dụ 2

Đầu vào: matrix[3][3] = {{1,1,1}, {2,2,2}, {3,3,3}}, k = 12

Đầu ra: Số ma trận con tổng chia hết cho k: 4

Phương pháp sử dụng

Duyệt ma trận từ trái sang phải. Với mỗi cặp cột trái-phải, cộng phần tử ma trận con vào mảng 1D arr[] và tính riêng tổng các phần tử và mảng con có tổng chia hết cho k.

• Hàm check_val(int arr[], int size, int k) nhận mảng 1D phần tử ma trận con, trả về số mảng con có tổng chia hết cho k.
• Tính tổng tích lũy, kiểm tra dư với k, lưu tần suất dư trong arr_2[].
• Duyệt arr_2[], với mỗi giá trị > 1 cộng arr_2[i] * (arr_2[i] - 1) / 2 vào đếm.
• Cộng thêm arr_2[0] vào đếm.
• Hàm matrix_divisible(int matrix[row][col], int size, int k) trả về số ma trận con tổng chia hết cho k.
• Khởi tạo count = 0, mảng tạm arr[size].
• Hai vòng lặp for đặt chỉ số cột trái i và phải j.
• Tính tổng phần tử: arr[temp] += matrix[temp][j].
• Cộng check_val(arr, size, k) vào count.
• Trả về count.

Ví dụ mã nguồn

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

Chạy mã trên cho kết quả:

Kết quả

Count of sub-matrices having sum divisible 'k' are: 7