行と列を交換することで生成できる一意の行列の数を見つける C++ プログラム

n x n の行列があるとします。行列の各要素は一意であり、1 から n² までの整数です。これで、次の操作を任意の数および順序で実行できるようになります。

• 行列 (1 ≤ x

• 行列 (1 ≤ x

• xy ≤ k であり、これらの値は同じ行と列に出現できないことに注意する必要があります。

操作を実行することで取得できる一意の行列の数を調べる必要があります。

したがって、入力が n = 3、k = 15、mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}} のような場合、出力は 36 になります。

たとえば、選択された 2 つの値は x = 3 と y = 5 です。列を交換すると、結果の行列は -

3 4 6
9 5 7
2 1 8

になります。このようにして、36 個の固有の行列を取得できます。

この問題を解決するには、次の手順に従います。

Define a function dfs(), this will take k, arrays ver and visited, one stack s.
   if visited[k] is non-zero, then:
      return
   visited[k] := true
   insert k into s
   for initialize iterator j := start of ver[k], when j is not equal to last element of ver[k], update (increase j by 1), do:
      dfs(*j, ver, visited, s)
Define an array f of size: 51.
f[0] := 1
for initialize i := 1, when i <= 50, update (increase i by 1), do:
   f[i] := (i * f[i - 1]) mod modval
Define an array e of size n
Define an array pk of size n
for initialize i := 0, when i < n, update (increase i by 1), do:
   for initialize j := i + 1, when j < n, update (increase j by 1), do:
      chk := 0
         for initialize l := 0, when l < n, update (increase l by 1), do:
            if (mat[i, l] + mat[j, l]) > k, then:
               chk := 1
               Come out from the loop
         if chk is same as 0, then:
             insert j at the end of pk[i]
             insert i at the end of pk[j]
          chk := 0
          for initialize l := 0, when l < n, update (increase l by 1), do:
             if (mat[l, i] + mat[l, j]) > k, then:
                chk := 1
                Come out from the loop
           if chk is same as 0, then:
               insert j at the end of e[i]
               insert i at the end of e[j]
resa := 1, resb = 1
Define an array v1 of size: n and v2 of size: n.
for initialize i := 0, when i < n, update (increase i by 1), do:
   v1[i] := false
   v2[i] := false
for initialize i := 0, when i < n, update (increase i by 1), do:
   Define one stack s.
   if not v1[i] is non-zero, then:
      dfs(i, pk, v1, s)
      if not s is empty, then:
         resa := resa * (f[size of s])
         resa := resa mod modval
for initialize i := 0, when i < n, update (increase i by 1), do:
   Define one stack s
   if not v2[i] is non-zero, then:
      dfs(i, e, v2, s)
      if not s is empty, then:
         resb := resb * (f[size of s])
         resb := resb mod modval
print((resa * resb) mod modval)

Example

理解を深めるために、次の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define modval 998244353
const int INF = 1e9;
void dfs(int k, vector<int> ver[], bool visited[], stack<int> &s) {
   if(visited[k])
      return;
   visited[k] = true;
   s.push(k);
   for(vector<int> :: iterator j = ver[k].begin(); j!=ver[k].end(); j++)
      dfs(*j, ver, visited, s);
}
void solve(int n, int k, vector<vector<int>> mat) {
   int f[51];
   f[0] = 1;
   for(int i = 1; i <= 50; i++) {
      f[i] = (i * f[i-1]) % modval;
   }
   vector<int> e[n];
   vector<int> pk[n];
   for(int i = 0; i < n; i++) {
      for(int j = i + 1;j < n; j++) {
         int chk = 0;
         for(int l = 0; l < n; l++){
            if((mat[i][l] + mat[j][l]) > k) {
               chk = 1;
               break;
            }
         }
         if(chk==0) {
            pk[i].push_back(j);
            pk[j].push_back(i);
         }
         chk = 0;
         for(int l = 0;l < n; l++) {
            if((mat[l][i] + mat[l][j]) > k){
               chk = 1;
               break;
            }
         }
         if(chk == 0) {
            e[i].push_back(j);
            e[j].push_back(i);
        }
      }
   }
   int resa = 1, resb = 1;
   bool v1[n], v2[n];
   for(int i = 0; i < n; i++) {
      v1[i] = false;
      v2[i] = false;
   }
   for(int i = 0;i < n; i++) {
      stack<int> s;
      if(!v1[i]) {
         dfs(i, pk, v1, s);
         if(!s.empty()) {
             resa *= (f[s.size()]) % modval;
             resa %= modval;
         }
      }
   }
   for(int i = 0 ;i < n; i++) {
      stack<int> s;
      if(!v2[i]){
         dfs(i, e, v2, s);
         if(!s.empty()) {
           resb *= (f[s.size()]) % modval;
            resb %= modval;
         }
      }
   }
   cout<< (resa * resb) % modval;
}
int main() {
   int n = 3, k = 15;
   vector<vector<int>> mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}};
   solve(n, k, mat);
   return 0;
}

Input

3, 15, {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}}

出力

36

以上が行と列を交換することで生成できる一意の行列の数を見つける C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。