#include #include #include #include // For std::swap #include // For scanf/printf // Using defines for constants as template arguments must be compile-time constants. #define MAX_N_VAL 200 #define MAX_M_VAL 200 #define MAX_CELLS_VAL (MAX_N_VAL * MAX_N_VAL) // Max N*N = 40000 #define MAX_OPS_VAL (6 * MAX_N_VAL - 2) // Max 6N-2 = 1198 for N=200. For N=1, it's 4. // Global arrays for basis, pivots, and canonical forms std::bitset basis[MAX_OPS_VAL]; int pivots[MAX_OPS_VAL]; int actual_rank = 0; // Number of vectors in the computed basis std::bitset board_canonical_forms[MAX_M_VAL]; char line_buffer[MAX_N_VAL + 5]; // Buffer for reading rows with scanf // Computes the basis for the vector space spanned by allowed operations. // The basis vectors are stored in `basis` array, their pivots in `pivots`. // `actual_rank` will store the dimension of this space. void compute_basis(int N) { if (N == 0) { // Problem constraint N >= 1, so this case won't be hit. actual_rank = 0; return; } // Store all fundamental operation vectors temporarily. // The number of fundamental ops is 6N-2 for N >= 1. std::vector> op_vecs_list; op_vecs_list.reserve( (N == 0) ? 0 : (6 * N -2) ); // Reserve space // Row operations (N of them) // For 0-indexed row r_idx for (int r_idx = 0; r_idx < N; ++r_idx) { std::bitset op_v; for (int c_idx = 0; c_idx < N; ++c_idx) { op_v[r_idx * N + c_idx] = 1; } op_vecs_list.push_back(op_v); } // Column operations (N of them) // For 0-indexed column c_idx for (int c_idx = 0; c_idx < N; ++c_idx) { std::bitset op_v; for (int r_idx = 0; r_idx < N; ++r_idx) { op_v[r_idx * N + c_idx] = 1; } op_vecs_list.push_back(op_v); } // Sum operations: r_idx + c_idx = k_sum (0-indexed sum) // k_sum from 0 to 2N-2. Total 2N-1 ops. for (int k_sum = 0; k_sum <= 2 * N - 2; ++k_sum) { std::bitset op_v; for (int r_idx = 0; r_idx < N; ++r_idx) { int c_idx = k_sum - r_idx; if (c_idx >= 0 && c_idx < N) { // Check if (r_idx, c_idx) is within grid op_v[r_idx * N + c_idx] = 1; } } op_vecs_list.push_back(op_v); } // Difference operations: r_idx - c_idx + (N-1) = k_diff_shifted (0-indexed shifted diff) // k_diff_shifted from 0 to 2N-2. Total 2N-1 ops. for (int k_diff_shifted = 0; k_diff_shifted <= 2 * N - 2; ++k_diff_shifted) { std::bitset op_v; int target_diff = k_diff_shifted - (N - 1); // Original difference r_idx - c_idx for (int r_idx = 0; r_idx < N; ++r_idx) { int c_idx = r_idx - target_diff; if (c_idx >= 0 && c_idx < N) { // Check if (r_idx, c_idx) is within grid op_v[r_idx * N + c_idx] = 1; } } op_vecs_list.push_back(op_v); } actual_rank = 0; int num_total_ops = op_vecs_list.size(); // Should be 6N-2 for N >= 1 // Gaussian elimination to find basis in Reduced Row Echelon Form (RREF) // Iterate through potential pivot columns (0 to N*N-1) // Iterate through rows of op_vecs_list to build basis up to 'actual_rank' for (int p_col = 0; p_col < N * N && actual_rank < num_total_ops; ++p_col) { int pivot_row_idx = actual_rank; // Find a row (from actual_rank onwards) that has a 1 in this p_col while (pivot_row_idx < num_total_ops && !op_vecs_list[pivot_row_idx][p_col]) { pivot_row_idx++; } if (pivot_row_idx < num_total_ops) { // Found a suitable row for pivot // Move this row to op_vecs_list[actual_rank] to be the next basis vector std::swap(op_vecs_list[actual_rank], op_vecs_list[pivot_row_idx]); // Record the pivot column for this new basis vector pivots[actual_rank] = p_col; // Eliminate the bit at p_col in all other rows in op_vecs_list // This step ensures the RRE form property (pivot column has 1 only at pivot row) for (int j = 0; j < num_total_ops; ++j) { if (j != actual_rank && op_vecs_list[j][p_col]) { op_vecs_list[j] ^= op_vecs_list[actual_rank]; } } actual_rank++; // Increment count of basis vectors found } } // Copy the computed basis vectors (which are now in op_vecs_list[0...actual_rank-1]) // to the global 'basis' array for use in get_canonical_form. for(int i = 0; i < actual_rank; ++i) { basis[i] = op_vecs_list[i]; } } // Computes canonical form of a given board state using the precomputed basis. std::bitset get_canonical_form(const std::bitset& board_state) { std::bitset canonical_form = board_state; // For each basis vector (they are in RRE form, pivots are strictly increasing) for (int i = 0; i < actual_rank; ++i) { // If the bit at the pivot position of this basis vector is set in the current canonical_form, // XOR with this basis vector to clear that bit. if (canonical_form[pivots[i]]) { canonical_form ^= basis[i]; } } return canonical_form; } int main() { // Using scanf/printf as suggested by the problem for performance. int N, M; scanf("%d %d", &N, &M); compute_basis(N); // Compute the basis once for the grid size N for (int m = 0; m < M; ++m) { std::bitset current_board; // Initialize to all zeros for (int r_idx = 0; r_idx < N; ++r_idx) { // Read N rows for the m-th board scanf("%s", line_buffer); for (int c_idx = 0; c_idx < N; ++c_idx) { // Read N characters for the r_idx-th row if (line_buffer[c_idx] == '#') { // Map (r_idx, c_idx) to a single index for bitset current_board[r_idx * N + c_idx] = 1; } } } board_canonical_forms[m] = get_canonical_form(current_board); } // Compare canonical forms and print results for (int i = 0; i < M - 1; ++i) { for (int j = i + 1; j < M; ++j) { if (board_canonical_forms[i] == board_canonical_forms[j]) { printf("1"); } else { printf("0"); } } printf("\n"); // Newline after each row of the output matrix } return 0; }