मान लीजिए, हमारे पास एक n x n मैट्रिक्स है। मैट्रिक्स में प्रत्येक तत्व अद्वितीय है और 1 और n 2 . के बीच एक पूर्णांक संख्या है . अब हम नीचे दिए गए कार्यों को किसी भी राशि और किसी भी क्रम में कर सकते हैं।
-
हम मैट्रिक्स में मौजूद कोई भी दो पूर्णांक 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