Table of Contents
1.Problem
2.Input
3.Output
4.Examples
4.1input
4.2output
5.Code
6.Conclusion
1.Problem
Cirno has prepared nn arrays of length nn each. Each array is a permutation of nn integers from 11 to nn. These arrays are special: for all 1≤i≤n1≤i≤n, if we take the ii-th element of each array and form another array of length nn with these elements, the resultant array is also a permutation of nn integers from 11 to nn. In the other words, if you put these nn arrays under each other to form a matrix with nn rows and nn columns, this matrix is a Latin square.
Afterwards, Cirno added additional nn arrays, each array is a permutation of nn integers from 11 to nn. For all 1≤i≤n1≤i≤n, there exists at least one position 1≤k≤n1≤k≤n, such that for the ii-th array and the (n + i)(n + i)-th array, the kk-th element of both arrays is the same. Notice that the arrays indexed from n + 1n + 1 to 2n2n don\ ‘t have to form a Latin square.
Also, Cirno made sure that for all 2n2n arrays, no two arrays are completely equal, i. e. for all pair of indices 1≤i
Finally, Cirno arbitrarily changed the order of 2n2n arrays.
AquaMoon calls a subset of all 2n2n arrays of size nn good if these arrays from a Latin square.
AquaMoon wants to know how many good subsets exist. Because this number may be particularly large, find it modulo 998244353998244353. Also, she wants to find any good subset. Can you help her?
2.Input
The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1001≤t≤100) – the number of test cases.
The first line of each test case contains a single integer nn (5≤n≤5005≤n≤500).
Then 2n2n lines followed. The ii-th of these lines contains nn integers, representing the ii-th array.
It is guaranteed that the sum of nn over all test cases does not exceed 500500.
3.Output
For each test case print two lines.
In the first line, print the number of good subsets by modulo 998244353998244353.
In the second line, print nn indices from 11 to 2n2n – indices of the nn arrays that form a good subset (you can print them in any order). If there are several possible answers – print any of them.
4.Examples
4.1input
3
7
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
4 5 6 7 1 2 3
5 6 7 1 2 3 4
6 7 1 2 3 4 5
7 1 2 3 4 5 6
1 2 3 4 5 7 6
1 3 4 5 6 7 2
1 4 5 6 7 3 2
1 5 6 7 4 2 3
1 6 7 5 2 3 4
1 7 6 2 3 4 5
1 7 2 3 4 5 6
5
4 5 1 2 3
3 5 2 4 1
1 2 3 4 5
5 2 4 1 3
3 4 5 1 2
2 3 4 5 1
1 3 5 2 4
4 1 3 5 2
2 4 1 3 5
5 1 2 3 4
6
2 3 4 5 6 1
3 1 2 6 4 5
6 1 2 3 4 5
5 6 1 3 2 4
4 3 6 5 2 1
5 6 1 2 3 4
4 5 6 1 2 3
3 4 5 6 1 2
1 2 3 4 5 6
2 5 4 1 6 3
3 2 5 4 1 6
1 4 3 6 5 2
4.2output
1
1 2 3 4 5 6 7
2
1 3 5 6 10
4
1 3 6 7 8 9
5.Code
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MOD = 998244353;
const int MAXN = 505;
const int MAXM = 1005;
vector<int> g[MAXM];
int col[MAXM], vis[MAXM], hv[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN];
int a[MAXM][MAXN];
queue<int> q;
template <typename T>
bool updateMax(T & amp; x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool updateMin(T & amp; x, T y) {
if (x > y) {
x = y;
return true;
}
return false;
}
int readint() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' & amp; & amp; ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void addedge(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
void dfs(int u, int color) {
col[u] = color;
for (int v : g[u]) {
if (col[v] == -1) {
dfs(v, color ^ 1);
}
}
}
void erase(int id) {
if (vis[id]) return;
for (int i = 1; i <= n; + + i) {
b[i][a[id][i]]--;
c[i][a[id][i]] -= id;
if (b[i][a[id][i]] == 1 & amp; & amp; !hv[i][a[id][i]]) {
q.push(i);
}
}
vis[id] = 1;
}
int main() {
int T = readint();
while (T--) {
int n = readint();
for (int i = 1; i <= n; + + i) {
for (int j = 1; j <= n; + + j) {
b[i][j] = c[i][j] = 0;
hv[i][j] = false;
}
g[i].clear();
}
for (int i = 1; i <= n + n; + + i) {
vis[i] = false;
col[i] = -1;
}
for (int i = 1; i <= n + n; + + i) {
for (int j = 1; j <= n; + + j) {
a[i][j] = readint();
b[j][a[i][j]] + + ;
c[j][a[i][j]] + = i;
}
}
for (int i = 1; i <= n; + + i) {
for (int j = 1; j <= n; + + j) {
if (b[i][j] == 1) {
q.push(i);
}
}
}
int cnt = 0;
while (!q.empty()) {
int t = q.front();
q.pop();
int pl = c[t][a[t]];
if (!pl || vis[pl]) continue;
vis[pl] = 1;
for (int i = 1; i <= n; + + i) {
b[i][a[pl][i]]--;
c[i][a[pl][i]] -= pl;
if (b[i][a[pl][i]] == 1 & amp; & amp; !hv[i][a[pl][i]]) {
q.push(i);
}
}
}
for (int i = 1; i <= n + n; + + i) {
if (!vis[i]) {
if (col[i] < 0) {
dfs(i, 0);
}
}
}
long long ans = 1LL << cnt;
cout << ans << endl;
vector<int> res;
for (int i = 1; i <= n + n; + + i) {
if (vis[i]) {
res.push_back(i);
}
}
for (int i = 1; i <= n + n; + + i) {
if (col[i] == 0) {
res.push_back(i);
}
}
sort(res.begin(), res.end());
for (int r : res) {
cout << r << ' ';
}
cout << endl;
}
return 0;
}
6.Conclusion
The core logic of this code is to solve a graph theory problem, which involves steps such as coloring, deletion operations, counting, and output. The core logic of the code is explained step by step below:
1. First, some constants and global variables are defined, including MOD (modulus), MAXN (maximum number of nodes), MAXM (maximum number of edges), as well as arrays and queues used to store graphs, coloring, access status, and numerical statistics. wait.
2. Two template functions updateMax and updateMin are defined to update the maximum and minimum values of variables.
3. Define a function readint, which is used to read an integer from the input stream.
4. Define a function added to add edges to the graph.
5. Define a recursive function dfs for depth-first search of the graph and coloring of nodes (only two colors). Among them, the incoming parameter u represents the current node, and color represents the color of the current node.
6. A function erase is defined to delete an edge. The specific operation is to reduce the corresponding value in the statistics array. If it is reduced to 1 and the corresponding node has not been visited, the node is added to the queue. At the same time, mark the edge’s status as deleted.
7. The main function performs graph initialization operations by reading input. The main steps include reading the number of test cases, reading the number of nodes, initializing the relevant array, reading the edge weights of the graph, etc.
8. After initialization, add nodes that appear only once to the queue according to the question requirements.
9. Next, use the breadth-first search idea to delete edges. By traversing the queue, edges are deleted in turn, and relevant statistical arrays and states are updated.
10. Finally, count the number of undeleted edges and output the results. Then add the deleted edges and dyed nodes to the result array respectively, and finally output the results in order.Generally speaking, the core logic of this code is to solve a graph theory problem, calculate the number of undeleted edges through steps such as coloring, deletion operations, breadth-first search, statistics and sorting, and output the results.
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 55444 people are learning the system