搜尋
首頁後端開發C++C++程式以找出透過交換行和列可以產生的唯一矩陣的數量

C++程式以找出透過交換行和列可以產生的唯一矩陣的數量

假設我們有一個 n x n 矩陣。矩陣中的每個元素都是唯一的,並且是 1 到 n2 之間的整數。現在我們可以以任意數量和任意順序執行以下操作。

  • 我們選擇矩陣中的任兩個整數 x 和 y,其中 (1 ≤ x

  • 我們選擇矩陣中的任兩個整數 x 和 y,其中 (1 ≤ x

  • 我們必須注意 x y ≤ k 且這些值不能出現在相同的行和列中。

我們必須找出透過執行操作可以獲得的唯一矩陣的數量。

因此,如果輸入類似於n = 3, k = 15, mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}},那麼輸出將為36。

例如,選取的兩個值是 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)

範例

讓我們看看以下實現,以便更好地理解-

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

輸入

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

輸出

36

以上是C++程式以找出透過交換行和列可以產生的唯一矩陣的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文轉載於:tutorialspoint。如有侵權,請聯絡admin@php.cn刪除
C#vs. C性能:基準測試和注意事項C#vs. C性能:基準測試和注意事項Apr 25, 2025 am 12:25 AM

C#和C 在性能上的差異主要體現在執行速度和資源管理上:1)C 在數值計算和字符串操作上通常表現更好,因為它更接近硬件,沒有垃圾回收等額外開銷;2)C#在多線程編程上更為簡潔,但性能略遜於C ;3)選擇哪種語言應根據項目需求和團隊技術棧決定。

C:死亡還是簡單地發展?C:死亡還是簡單地發展?Apr 24, 2025 am 12:13 AM

1)c relevantduetoItsAverity and效率和效果臨界。 2)theLanguageIsconTinuellyUped,withc 20introducingFeaturesFeaturesLikeTuresLikeSlikeModeLeslikeMeSandIntIneStoImproutiMimproutimprouteverusabilityandperformance.3)

C在現代世界中:應用和行業C在現代世界中:應用和行業Apr 23, 2025 am 12:10 AM

C 在現代世界中的應用廣泛且重要。 1)在遊戲開發中,C 因其高性能和多態性被廣泛使用,如UnrealEngine和Unity。 2)在金融交易系統中,C 的低延遲和高吞吐量使其成為首選,適用於高頻交易和實時數據分析。

C XML庫:比較和對比選項C XML庫:比較和對比選項Apr 22, 2025 am 12:05 AM

C 中有四種常用的XML庫:TinyXML-2、PugiXML、Xerces-C 和RapidXML。 1.TinyXML-2適合資源有限的環境,輕量但功能有限。 2.PugiXML快速且支持XPath查詢,適用於復雜XML結構。 3.Xerces-C 功能強大,支持DOM和SAX解析,適用於復雜處理。 4.RapidXML專注於性能,解析速度極快,但不支持XPath查詢。

C和XML:探索關係和支持C和XML:探索關係和支持Apr 21, 2025 am 12:02 AM

C 通過第三方庫(如TinyXML、Pugixml、Xerces-C )與XML交互。 1)使用庫解析XML文件,將其轉換為C 可處理的數據結構。 2)生成XML時,將C 數據結構轉換為XML格式。 3)在實際應用中,XML常用於配置文件和數據交換,提升開發效率。

C#vs. C:了解關鍵差異和相似之處C#vs. C:了解關鍵差異和相似之處Apr 20, 2025 am 12:03 AM

C#和C 的主要區別在於語法、性能和應用場景。 1)C#語法更簡潔,支持垃圾回收,適用於.NET框架開發。 2)C 性能更高,需手動管理內存,常用於系統編程和遊戲開發。

C#與C:歷史,進化和未來前景C#與C:歷史,進化和未來前景Apr 19, 2025 am 12:07 AM

C#和C 的歷史與演變各有特色,未來前景也不同。 1.C 由BjarneStroustrup在1983年發明,旨在將面向對象編程引入C語言,其演變歷程包括多次標準化,如C 11引入auto關鍵字和lambda表達式,C 20引入概念和協程,未來將專注於性能和系統級編程。 2.C#由微軟在2000年發布,結合C 和Java的優點,其演變注重簡潔性和生產力,如C#2.0引入泛型,C#5.0引入異步編程,未來將專注於開發者的生產力和雲計算。

C#vs. C:學習曲線和開發人員的經驗C#vs. C:學習曲線和開發人員的經驗Apr 18, 2025 am 12:13 AM

C#和C 的学习曲线和开发者体验有显著差异。1)C#的学习曲线较平缓,适合快速开发和企业级应用。2)C 的学习曲线较陡峭,适用于高性能和低级控制的场景。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器