P1734E

First, analyze the second condition: rearrange it to $a_{r_1, c_1} - a_{r_1, c_2} \not\equiv a_{r_2, c_1} - a_{r_2, c_2} \pmod{n}$. Our goal is to ensure that the column-wise difference values between any two rows are distinct. We have not yet addressed conditions 1 and 3. Conddition 1 can be satisfied by taking all elements modulo $n$. For condition 3, note that adding a constant to every element in a single row does not affect column-wise differences, so we only need to enforce the second condition.

To satisfy the second condition, we need the pairwise row-wise remainder differances for any two columns to be unique. We can use remainders from $0$ to $n-1$ for this. A valid base construction is $a_{i,j} = (i \cdot j) \pmod{n}$, but we need to adjust each row to match the given target values for the diagonal elements.

When $n$ is prime, the required uniqueness of differences holds because for any $k \in [1, n-1]$, $k$ is coprime to $n$, so $ak \not\equiv bk \pmod{n}$ for $a \neq b$.

#include <iostream>
#include <vector>
using namespace std;

const int MAX_GRID_SIZE = 505;
int grid_size, row_offset[MAX_GRID_SIZE], grid[MAX_GRID_SIZE][MAX_GRID_SIZE];

int main() {
    cin >> grid_size;
    for (int i = 1; i <= grid_size; ++i) {
        cin >> row_offset[i];
    }

    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            grid[i][j] = (1LL * i * j) % grid_size;
        }
    }

    for (int i = 1; i <= grid_size; ++i) {
        int adjust = (row_offset[i] - grid[i][i] + grid_size) % grid_size;
        for (int j = 1; j <= grid_size; ++j) {
            grid[i][j] = (grid[i][j] + adjust) % grid_size;
        }
    }

    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

P1375E

Without the restriction of only swapping adjacent inversions, this problem reduces to a bubble sort-like process. Our approach is to place the element with the largest relative order at the end of the array, while preserving the relative order of all preceding elements.

Define relative element size first: for two elements, compare their numerical values first; if equal, compare their original indices. Preserving relative position means the before-after order of any two elements' relative sizes remains unchanged.

The procedure is: repeatedly place the largest remaining relative order element at the current end of the array, then process the first $n-1$ elements. Specifically, for each element with relative rank $k$, swap it with the current end position until all elements with higher relative rank are moved past it.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

const int MAX_ARR_SIZE = 100010;
int arr[MAX_ARR_SIZE], sorted_arr[MAX_ARR_SIZE], pos[MAX_ARR_SIZE];
map<int, int> rank_count, start_rank;
vector<pair<int, int>> swap_ops;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        sorted_arr[i] = arr[i];
        rank_count[arr[i]]++;
    }

    sort(sorted_arr + 1, sorted_arr + 1 + n);
    start_rank[0] = 1;
    for (int i = 1; i <= n; ++i) {
        if (sorted_arr[i] != sorted_arr[i-1]) {
            start_rank[sorted_arr[i]] = start_rank[sorted_arr[i-1]] + rank_count[sorted_arr[i-1]];
        }
    }

    for (int i = 1; i <= n; ++i) {
        arr[i] = start_rank[arr[i]]++;
    }

    for (int current_end = n; current_end >= 1; --current_end) {
        for (int i = 1; i <= current_end; ++i) {
            pos[arr[i]] = i;
        }
        for (int r = arr[current_end] + 1; r <= current_end; ++r) {
            swap_ops.emplace_back(pos[r], current_end);
            swap(arr[pos[r]], arr[current_end]);
        }
    }

    cout << swap_ops.size() << endl;
    for (auto &p : swap_ops) {
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}

P1745

First simplify the problem by considering trees instead of general graphs. For a node $u$, if all its child nodes already satisfy the required state, we can traverse to its parent node and back, then return to $u$. For the root node (node 1) which has no parent, after processing all children, we can adjust its state by visiting one child node and backtracking again.

For general graphs, first build a spanning tree of the graph, then apply the tree-based traversal logic to adjust all node states to the target values.

#include <iostream>
#include <vector>
using namespace std;

const int MAX_NODE = 1000010;
int n, m, visited[MAX_NODE], parent[MAX_NODE], node_state[MAX_NODE];
vector<int> adj[MAX_NODE], tree_adj[MAX_NODE];
vector<int> traversal_ops;

void build_spanning_tree(int u) {
    visited[u] = 1;
    for (int v : adj[u]) {
        if (!visited[v]) {
            tree_adj[u].push_back(v);
            parent[v] = u;
            build_spanning_tree(v);
        }
    }
}

void flip_node(int x) {
    traversal_ops.push_back(x);
    node_state[x] ^= 1;
}

void dfs_traversal(int u) {
    flip_node(u);
    for (int v : tree_adj[u]) {
        dfs_traversal(v);
        flip_node(u);
    }
    if (node_state[u] == 1) {
        if (u == 1) {
            flip_node(tree_adj[u][0]);
            flip_node(u);
            flip_node(tree_adj[u][0]);
        } else {
            flip_node(parent[u]);
            flip_node(u);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) {
        char c;
        cin >> c;
        node_state[i] = (c == '1');
    }

    build_spanning_tree(1);
    dfs_traversal(1);

    cout << traversal_ops.size() << endl;
    for (int x : traversal_ops) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}