สมมุติว่าเรามีเมทริกซ์ขนาด 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
