สมมติว่าเรามีเมทริกซ์ขนาด n x n แต่ละองค์ประกอบในเมทริกซ์มีค่าไม่ซ้ำกันและเป็นจำนวนเต็มระหว่าง 1 ถึง n2 ตอนนี้เราสามารถดำเนินการต่อไปนี้ในปริมาณและลำดับใดก็ได้
เราเลือกจำนวนเต็ม 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 เมทริกซ์ด้วยวิธีนี้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้ -
กำหนดฟังก์ชัน dfs() ซึ่งรับ k, อาร์เรย์ ver และ visited, สแต็ก s
ถ้า visited[k] ไม่เป็นศูนย์ แล้ว:
return
visited[k] := true
ใส่ k ลงใน s
สำหรับตัววนซ้ำ j := เริ่มต้นของ ver[k], เมื่อ j ไม่เท่ากับองค์ประกอบสุดท้ายของ ver[k], เพิ่ม j ขึ้นทีละ 1, ทำ:
dfs(*j, ver, visited, s)
กำหนดอาร์เรย์ f ขนาด: 51. f[0] := 1
สำหรับ i := 1, เมื่อ i <= 50, เพิ่ม i ขึ้นทีละ 1, ทำ:
f[i] := (i * f[i - 1]) mod modval
กำหนดอาร์เรย์ e ขนาด n
กำหนดอาร์เรย์ pk ขนาด n
สำหรับ i := 0, เมื่อ i < n, เพิ่ม i ขึ้นทีละ 1, ทำ:
สำหรับ j := i + 1, เมื่อ j < n, เพิ่ม j ขึ้นทีละ 1, ทำ:
chk := 0
สำหรับ l := 0, เมื่อ l < n, เพิ่ม l ขึ้นทีละ 1, ทำ:
ถ้า (mat[i, l] + mat[j, l]) > k, แล้ว:
chk := 1
ออกจากลูป
ถ้า chk เท่ากับ 0, แล้ว:
ใส่ j ที่ท้ายของ pk[i]
ใส่ i ที่ท้ายของ pk[j]
chk := 0
สำหรับ l := 0, เมื่อ l < n, เพิ่ม l ขึ้นทีละ 1, ทำ:
ถ้า (mat[l, i] + mat[l, j]) > k, แล้ว:
chk := 1
ออกจากลูป
ถ้า chk เท่ากับ 0, แล้ว:
ใส่ j ที่ท้ายของ e[i]
ใส่ i ที่ท้ายของ e[j]
resa := 1, resb = 1
กำหนดอาร์เรย์ v1 ขนาด: n และ v2 ขนาด: n.
สำหรับ i := 0, เมื่อ i < n, เพิ่ม i ขึ้นทีละ 1, ทำ:
v1[i] := false
v2[i] := false
สำหรับ i := 0, เมื่อ i < n, เพิ่ม i ขึ้นทีละ 1, ทำ:
กำหนดสแต็ก s.
ถ้า not v1[i] ไม่เป็นศูนย์, แล้ว:
dfs(i, pk, v1, s)
ถ้า not s ว่าง, แล้ว:
resa := resa * (f[ขนาดของ s])
resa := resa mod modval
สำหรับ i := 0, เมื่อ i < n, เพิ่ม i ขึ้นทีละ 1, ทำ:
กำหนดสแต็ก s
ถ้า not v2[i] ไม่เป็นศูนย์, แล้ว:
dfs(i, e, v2, s)
ถ้า not s ว่าง, แล้ว:
resb := resb * (f[ขนาดของ s])
resb := resb mod modval
พิมพ์((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
