假设我们有一个 n x n 矩阵。矩阵中的每个元素都是唯一的，并且是 1 到 n2 之间的整数。现在我们可以以任意数量和任意顺序执行以下操作。
我们选择矩阵中的任意两个整数 x 和 y，其中 (1 ≤ x
我们选择矩阵中的任意两个整数 x 和 y，其中 (1 ≤ x
我们必须注意 x + y ≤ k 并且这些值不能出现在相同的行和列中。
立即学习“C++免费学习笔记（深入）”；
我们必须找出通过执行操作可以获得的唯一矩阵的数量。
因此，如果输入类似于 n = 3, k = 15, mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}}，那么输出将为36。
例如，选择的两个值是 x = 3 和 y = 5。如果交换列，所得矩阵将是 –
3 4 69 5 72 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] := 1for 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 = 1Define an array v1 of size: n and v2 of size: n.for initialize i := 0, when i示例
让我们看看以下实现，以便更好地理解 -
#include using namespace std;#define modval 998244353const int INF = 1e9;void dfs(int k, vector ver[], bool visited[], stack &s) { if(visited[k]) return; visited[k] = true; s.push(k); for(vector :: iterator j = ver[k].begin(); j!=ver[k].end(); j++) dfs(*j, ver, visited, s);}void solve(int n, int k, vector> mat) { int f[51]; f[0] = 1; for(int i = 1; i e[n]; vector 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;}登录后复制
输入
3, 15, {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}}登录后复制
输出
36登录后复制
以上就是C++程序以找出通过交换行和列可以生成的唯一矩阵的数量的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2584443.html
