C++ प्रोग्राम: पंक्तियों और स्तंभों की अदला-बदली से उत्पन्न अद्वितीय मैट्रिक्स की संख्या ज्ञात करना

समस्या विवरण

मान लीजिए हमारे पास एक n x n मैट्रिक्स है। मैट्रिक्स में प्रत्येक तत्व अद्वितीय है और 1 से n² के बीच की एक पूर्णांक संख्या है। हम निम्नलिखित ऑपरेशन किसी भी क्रम में और कितनी भी बार कर सकते हैं:

• मैट्रिक्स में मौजूद किन्हीं दो पूर्णांकों x और y को चुनें, जहां (1 ≤ x < y ≤ n), और x और y वाले स्तंभों की अदला-बदली करें।
• मैट्रिक्स में मौजूद किन्हीं दो पूर्णांकों x और y को चुनें, जहां (1 ≤ x < y ≤ n), और x और y वाली पंक्तियों की अदला-बदली करें।
• ध्यान दें कि 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 अद्वितीय मैट्रिक्स प्राप्त किए जा सकते हैं।

हल का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

1. DFS फंक्शन परिभाषित करें जो k, ver सरणी, visited सरणी और एक स्टैक s लेता है।
2. फैक्टोरियल सरणी f की गणना करें जहां f[i] = (i * f[i-1]) % modval
3. दो ग्राफ बनाएं:
   • pk[i] - वे पंक्तियाँ जिन्हें आपस में बदला जा सकता है
   • e[i] - वे स्तंभ जिन्हें आपस में बदला जा सकता है
4. कनेक्टेड कॉम्पोनेंट्स खोजें DFS का उपयोग करके दोनों ग्राफ में
5. परिणाम की गणना करें प्रत्येक कॉम्पोनेंट के आकार के फैक्टोरियल को गुणा करके

एल्गोरिदम

// pk ग्राफ: पंक्तियों i और j के लिए, यदि सभी स्तंभों l के लिए mat[i][l] + mat[j][l] ≤ k है, तो i और j को जोड़ें
// e ग्राफ: स्तंभों i और j के लिए, यदि सभी पंक्तियों l के लिए mat[l][i] + mat[l][j] ≤ k है, तो i और j को जोड़ें

// प्रत्येक ग्राफ में कनेक्टेड कॉम्पोनेंट्स खोजें
// प्रत्येक कॉम्पोनेंट के आकार के फैक्टोरियल को गुणा करें
// अंतिम उत्तर = (resa * resb) % modval

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 
#define modval 998244353 

void dfs(int k, vector<int> ver[], bool visited[], stack<int> &s) {
    if(visited[k]) return;
    visited[k] = true;
    s.push(k);
    for(auto 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] = (1LL * i * f[i-1]) % modval;

    vector<int> e[n], pk[n];
    
    // pk ग्राफ बनाएं (पंक्तियों के लिए)
    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);
            }
        }
    }
    
    // e ग्राफ बनाएं (स्तंभों के लिए)
    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[l][i] + mat[l][j]) > k) {
                    chk = 1;
                    break;
                }
            }
            if(chk == 0) {
                e[i].push_back(j);
                e[j].push_back(i);
            }
        }
    }

    long long resa = 1, resb = 1;
    vector<bool> v1(n, false), v2(n, false);
    
    // pk ग्राफ में कनेक्टेड कॉम्पोनेंट्स
    for(int i = 0; i < n; i++) {
        if(!v1[i]) {
            stack<int> s;
            dfs(i, pk, v1.data(), s);
            if(!s.empty()) {
                resa = (resa * f[s.size()]) % modval;
            }
        }
    }
    
    // e ग्राफ में कनेक्टेड कॉम्पोनेंट्स
    for(int i = 0; i < n; i++) {
        if(!v2[i]) {
            stack<int> s;
            dfs(i, e, v2.data(), s);
            if(!s.empty()) {
                resb = (resb * f[s.size()]) % 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

जटिलता विश्लेषण

• समय जटिलता: O(n³) - तीन नेस्टेड लूप के कारण
• स्पेस जटिलता: O(n²) - ग्राफ संग्रहण के लिए