C++で合計が割り切れる「k」を持つ部分行列を数えます

入力として行x列行列が与えられます。目標は、行列[row] [col]内のすべての部分行列を見つけて、その部分行列の要素の合計が整数kで割り切れるようにすることです。

行列がmat[3][3]で、kが4の場合、部分行列は次のようになります。-

例を挙げて理解しましょう。

例

入力- matrix [3] [3] ={{1,1,1}、{2,2,2}、{3,3,3}} k =4

出力- 合計が割り切れる「k」を持つ部分行列の数は次のとおりです。4

説明- 部分行列は上記のようになります。

入力- matrix [3] [3] ={{1,1,1}、{2,2,2}、{3,3,3}} k =12

出力- 合計が割り切れる「k」を持つ部分行列の数は次のとおりです。4

説明- 部分行列は次のようになります：-

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、行列を左から右にトラバースし、左右の列の各ペアについて、部分行列の要素を配列arr []に追加し、その要素の合計と、合計がkで割り切れる部分配列を個別に計算します。

関数check_val（）は、部分行列の要素を持つ配列を1D配列として受け取ります。次に、累積合計を計算し、kを使用して剰余をチェックし、剰余の頻度を配列arr_2[]に格納します。

• matrix[row][col]と整数kを入力として受け取ります。
• 関数check_val（int arr []、int size、int k）は、部分行列の要素のarr []を取り、合計がkで割り切れるarr内のすべてのサブ配列の数を返します。
• 変数のカウントと温度を0とします。
• kを使用した累積合計の余りの頻度を格納するために配列arr_2[]を取得します。
• i=0からi
• forループトラバース頻度配列arr_2[]を再度使用し、値ごとに> 1 arr_2 [i] *（arr_2 [i] --1））/ 2を追加して、可能なすべてのサブ配列の数としてカウントします。
• 最後に、カウントするarr_2[0]を追加します。
• 関数matrix_divisible（int matrix [row] [col]、int size、int k）は、入力部分行列を受け取り、合計がkで割り切れるすべての部分行列の数を返します。
• 初期カウントを0とします。
• 一時配列arr[size]を取得します。
• 2つのforループを使用して、左の列のインデックスiと右の列のインデックスjを設定します。
• 要素の合計をarr[temp]+ =matrix[temp][j]として計算します。
• arr []のサブ配列の数については、check_val（arr、size、k）を追加してカウントします。
• すべてのforループの最後に、結果としてカウントを返します。

例

#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