
假设我们有一个 n x n 矩阵。矩阵中的每个元素都是唯一的,并且是 1 到 n2 之间的整数。现在我们可以以任意数量和任意顺序执行以下操作。
我们选择矩阵中的任意两个整数 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 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 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 <h2>示例</h2><p>让我们看看以下实现,以便更好地理解 -</p><pre class="brush:cpp;toolbar:false;">#include <bits>
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>> mat) {
int f[51];
f[0] = 1;
for(int i = 1; i e[n];
vector<int> pk[n];
for(int i = 0; i k) {
chk = 1;
break;
}
}
if(chk==0) {
pk[i].push_back(j);
pk[j].push_back(i);
}
chk = 0;
for(int l = 0;l 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 s;
if(!v1[i]) {
dfs(i, pk, v1, s);
if(!s.empty()) {
resa *= (f[s.size()]) % modval;
resa %= modval;
}
}
}
for(int i = 0 ;i s;
if(!v2[i]){
dfs(i, e, v2, s);
if(!s.empty()) {
resb *= (f[s.size()]) % modval;
resb %= modval;
}
}
}
cout> mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}};
solve(n, k, mat);
return 0;
}</int></vector></int></int></int></bits>
输入
3, 15, {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}}
输出
36
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











