C++ প্রোগ্রাম: সারি ও কলাম বদলি করে יোনিক ম্যাট্রিক্সের সংখ্যা বের করা

ধরি, আমাদের কাছে একটি n x n ম্যাট্রিক্স আছে। ম্যাট্রিক্সের প্রতিটি উপাদান ইউনিক এবং ১ থেকে 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}} হলে আউটপুট হবে ৩৬।

যেমন, x = 3 এবং y = 5 বেছে নিলে কলাম বদলি করার পর ম্যাট্রিক্সটি হবে:

3 4 6 9 5 7 2 1 8

এভাবে ৩৬টি ইউনিক ম্যাট্রিক্স পাওয়া যায়।

সমাধানের পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করা হবে:

ফাংশন dfs() ডিফাইন করুন, যা k, ver অ্যারে, visited অ্যারে এবং একটি স্ট্যাক s নেবে।
if visited[k] নন-জিরো হলে, return করুন।
visited[k] := true
k কে s-তে ইন্সার্ট করুন
ver[k]-এর শুরু থেকে শেষ পর্যন্ত j এর জন্য:
    dfs(*j, ver, visited, s)

৫১ আকারের একটি f অ্যারে ডিফাইন করুন। f[0] := 1
i = 1 থেকে ৫০ পর্যন্ত:
    f[i] := (i * f[i-1]) mod modval

n আকারের e এবং pk অ্যারে ডিফাইন করুন
i = 0 থেকে n-1 পর্যন্ত:
    j = i+1 থেকে n-1 পর্যন্ত:
        chk := 0
        l = 0 থেকে n-1 পর্যন্ত:
            if (mat[i][l] + mat[j][l]) > k, তবে:
                chk := 1
                লুপ থেকে বের হোন
        if chk == 0, তবে:
            pk[i]-তে j যোগ করুন
            pk[j]-তে i যোগ করুন
        chk := 0
        l = 0 থেকে n-1 পর্যন্ত:
            if (mat[l][i] + mat[l][j]) > k, তবে:
                chk := 1
                লুপ থেকে বের হোন
        if chk == 0, তবে:
            e[i]-তে j যোগ করুন
            e[j]-তে i যোগ করুন

resa := 1, resb := 1
n আকারের v1 এবং v2 অ্যারে ডিফাইন করুন
i = 0 থেকে n-1 পর্যন্ত:
    v1[i] := false
    v2[i] := false

i = 0 থেকে n-1 পর্যন্ত:
    একটি স্ট্যাক s ডিফাইন করুন
    if not v1[i], তবে:
        dfs(i, pk, v1, s)
        if s খালি না হয়, তবে:
            resa := resa * (f[s.size()]) mod modval

i = 0 থেকে n-1 পর্যন্ত:
    একটি স্ট্যাক s ডিফাইন করুন
    if not v2[i], তবে:
        dfs(i, e, v2, s)
        if s খালি না হয়, তবে:
            resb := resb * (f[s.size()]) 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}}