#include #include #include #include // For std::min // Use unsigned 32-bit integers for LCG state and parameters. // This type automatically handles arithmetic modulo 2^32 due to overflow behavior. using uint32 = unsigned int; // Use unsigned 64-bit integers for counts and positions, as they can exceed 2^32. using uint64 = unsigned long long; // Structure for 2x2 matrix operations modulo 2^32. // Used to efficiently compute the LCG state after many steps. struct Matrix { uint32 mat[2][2]; Matrix() { mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0; } }; // Matrix multiplication C = A * B, performed modulo 2^32. Matrix multiply(const Matrix& A, const Matrix& B) { Matrix C; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { // Use uint64 for intermediate sum calculation to prevent overflow before the final modulo 2^32. // The product of two uint32 can reach (2^32-1)^2, which fits into uint64. // The sum of two such products can exceed uint64 capacity, but since we only need the result modulo 2^32, // casting the final sum to uint32 achieves this implicitly. uint64 sum = 0; for (int k = 0; k < 2; ++k) { // Perform multiplications using uint64 to hold the possibly large intermediate product. sum = sum + (uint64)A.mat[i][k] * B.mat[k][j]; } // Casting sum to uint32 effectively computes sum mod 2^32. C.mat[i][j] = (uint32)sum; } } return C; } // Matrix power M^p using binary exponentiation (exponentiation by squaring). // Computes M^p modulo 2^32 efficiently in O(log p) matrix multiplications. Matrix matrix_pow(Matrix M, uint64 p) { Matrix res; // Initialize result matrix to identity matrix. res.mat[0][0] = 1; res.mat[1][1] = 1; // Standard binary exponentiation algorithm. while (p > 0) { // If p is odd, multiply current result by M. if (p & 1) { res = multiply(res, M); } // Square M for the next iteration. M = multiply(M, M); // Halve p (integer division). p >>= 1; } return res; } int main() { // Use faster I/O operations. std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); uint32 a, b, x0; // LCG parameters and initial seed. uint64 N; // Number of turns per player. std::cin >> a >> b >> x0 >> N; // Base case: If N=0, no turns are taken, scores are 0. if (N == 0) { std::cout << "0 0\n"; return 0; } // Total turns in the game is 2*N. uint64 total_turns = 2 * N; // Game state variables: positions and stone counts for Takahashi (T) and Aoki (A). uint64 P_T = 0, P_A = 0; // Current positions. uint64 B_T = 0, W_T = 0; // Black and White stone counts for Takahashi. uint64 B_A = 0, W_A = 0; // Black and White stone counts for Aoki. // Find cycle in the sequence y_k = x_k mod 6. // This sequence determines the die rolls d_k = y_k + 1. std::map visited_y; // Map to store {y_value -> first turn k it appeared}. uint32 y; // Current y_k value. uint64 k_cycle_found = 0; // Turn index when cycle is detected. 0 if not found within total_turns. uint64 mu = 0; // Length of the preperiod (transient part before cycle). uint64 lambda = 0; // Length of the cycle. // Simulate LCG to find cycle properties. Use a temporary variable for x state. uint32 temp_x = x0; for (uint64 k = 1; k <= total_turns; ++k) { // Calculate next LCG state x_k. temp_x = a * temp_x + b; // Calculate y_k = x_k mod 6. y = temp_x % 6; // Check if this y value has been seen before. if (visited_y.count(y)) { // Cycle detected. k_cycle_found = k; // Record the turn index. mu = visited_y[y] - 1; // Preperiod length is steps before first occurrence. lambda = k - visited_y[y]; // Cycle length is difference in turn indices. break; // Exit loop once cycle is found. } // Store the first occurrence of this y value and its turn index. visited_y[y] = k; // If loop reaches total_turns without finding a cycle, it means the relevant part of the sequence fits entirely within the preperiod. if (k == total_turns) { mu = total_turns; // The entire sequence up to total_turns is considered preperiod. lambda = 0; // No cycle is relevant/used. k_cycle_found = k+1; // Set flag to indicate loop finished, treated as cycle found after end. break; } } // Simulate the preperiod phase (first mu steps). uint32 current_x = x0; // Initialize LCG state for actual game simulation. for (uint64 k = 1; k <= mu; ++k) { // Update LCG state. current_x = a * current_x + b; // Calculate die roll. uint32 roll = (current_x % 6) + 1; // Determine whose turn it is based on turn index k (odd for T, even for A). if (k % 2 != 0) { // Takahashi's turn P_T += roll; // Update position. // Check parity of new position and update stone counts. if (P_T % 2 != 0) B_T++; else W_T++; } else { // Aoki's turn P_A += roll; // Update position. // Check parity and update stone counts. if (P_A % 2 != 0) B_A++; else W_A++; } } // Store the LCG state after the preperiod phase. uint32 x_mu = current_x; // Calculate remaining turns after the preperiod. uint64 remaining_turns = total_turns - mu; // If there is a cycle (lambda > 0) and there are remaining turns: if (lambda > 0 && remaining_turns > 0) { // Calculate number of full cycles (q) and remaining steps within the last partial cycle (r). uint64 q = remaining_turns / lambda; uint64 r = remaining_turns % lambda; // Calculate the changes in state over one full cycle. // Simulate one cycle starting from a temporary state to find deltas. uint32 cycle_sim_x = x_mu; // Start LCG state from x_mu. uint64 cycle_delta_PT = 0, cycle_delta_PA = 0; // Position changes over one cycle. uint64 cycle_delta_BT0 = 0, cycle_delta_WT0 = 0; // Stone count changes assuming Player T starts cycle at even position. uint64 cycle_delta_BA0 = 0, cycle_delta_WA0 = 0; // Stone count changes assuming Player A starts cycle at even position. uint64 temp_PT = 0; // Use temporary positions starting at 0 to track parity for delta calculation. uint64 temp_PA = 0; // Simulate lambda steps to find cycle deltas. for (uint64 i = 1; i <= lambda; ++i) { cycle_sim_x = a * cycle_sim_x + b; uint32 roll = (cycle_sim_x % 6) + 1; uint64 current_turn_idx = mu + i; // Absolute turn index within the game. // Check whose turn based on absolute turn index. if (current_turn_idx % 2 != 0) { // Takahashi's turn temp_PT += roll; // Update temporary position. cycle_delta_PT += roll; // Accumulate position change. // Accumulate stone counts based on temporary position's parity (assumes start even). if (temp_PT % 2 != 0) cycle_delta_BT0++; else cycle_delta_WT0++; } else { // Aoki's turn temp_PA += roll; cycle_delta_PA += roll; if (temp_PA % 2 != 0) cycle_delta_BA0++; else cycle_delta_WA0++; } } // Define the single step LCG transformation matrix M1 = {{a, b}, {0, 1}}. Matrix M1; M1.mat[0][0] = a; M1.mat[0][1] = b; M1.mat[1][0] = 0; M1.mat[1][1] = 1; // Compute M^lambda, the transformation matrix over one cycle. Matrix M_lambda = matrix_pow(M1, lambda); // Compute (M^lambda)^q, the transformation over q full cycles. Matrix M_lambda_q = matrix_pow(M_lambda, q); // Update player positions based on total change over q cycles. P_T += q * cycle_delta_PT; P_A += q * cycle_delta_PA; // Calculate total stone changes over q cycles, considering initial parity and parity change per cycle. uint64 total_delta_BT = 0, total_delta_WT = 0; uint64 total_delta_BA = 0, total_delta_WA = 0; // Check parity of Takahashi's position at the start of the cycles (after mu steps). bool P_T_parity_at_mu_is_odd = ( (mu == 0 ? 0 : P_T) % 2 != 0); // P_T is state after mu steps. If mu=0, initial P_T=0. // Check if Takahashi's position parity changes over one cycle. bool cycle_delta_PT_odd = (cycle_delta_PT % 2 != 0); // Calculate total stone changes for Takahashi over q cycles. if (!cycle_delta_PT_odd) { // If parity change is even, parity remains constant throughout cycles. if (!P_T_parity_at_mu_is_odd) { // Starts even. total_delta_BT = q * cycle_delta_BT0; total_delta_WT = q * cycle_delta_WT0; } else { // Starts odd. Stone collection swaps roles (B collected where W would be, etc.). total_delta_BT = q * cycle_delta_WT0; // Use WT0 for BT count when starting odd. total_delta_WT = q * cycle_delta_BT0; // Use BT0 for WT count when starting odd. } } else { // If parity change is odd, parity alternates each cycle. uint64 count_p1 = q / 2; // Number of cycles starting with parity 1-P_T_parity_at_mu_is_odd uint64 count_p0 = q - count_p1; // Number of cycles starting with parity P_T_parity_at_mu_is_odd if (!P_T_parity_at_mu_is_odd) { // Starts even (p0=0). total_delta_BT = count_p0 * cycle_delta_BT0 + count_p1 * cycle_delta_WT0; // Sum contributions based on starting parity of each cycle. total_delta_WT = count_p0 * cycle_delta_WT0 + count_p1 * cycle_delta_BT0; } else { // Starts odd (p0=1). total_delta_BT = count_p0 * cycle_delta_WT0 + count_p1 * cycle_delta_BT0; // Contributions are swapped compared to starting even. total_delta_WT = count_p0 * cycle_delta_BT0 + count_p1 * cycle_delta_WT0; } } // Repeat similar calculation for Aoki's stones. bool P_A_parity_at_mu_is_odd = ( (mu == 0 ? 0 : P_A) % 2 != 0); // Check Aoki's start parity after mu steps. bool cycle_delta_PA_odd = (cycle_delta_PA % 2 != 0); // Check parity change for Aoki over cycle. if (!cycle_delta_PA_odd) { // Constant parity for Aoki. if (!P_A_parity_at_mu_is_odd) { // Starts even. total_delta_BA = q * cycle_delta_BA0; total_delta_WA = q * cycle_delta_WA0; } else { // Starts odd. total_delta_BA = q * cycle_delta_WA0; total_delta_WA = q * cycle_delta_BA0; } } else { // Alternating parity for Aoki. uint64 count_p1 = q / 2; uint64 count_p0 = q - count_p1; if (!P_A_parity_at_mu_is_odd) { // Starts even. total_delta_BA = count_p0 * cycle_delta_BA0 + count_p1 * cycle_delta_WA0; total_delta_WA = count_p0 * cycle_delta_WA0 + count_p1 * cycle_delta_BA0; } else { // Starts odd. total_delta_BA = count_p0 * cycle_delta_WA0 + count_p1 * cycle_delta_BA0; total_delta_WA = count_p0 * cycle_delta_BA0 + count_p1 * cycle_delta_WA0; } } // Apply the calculated total stone changes to the game state. B_T += total_delta_BT; W_T += total_delta_WT; B_A += total_delta_BA; W_A += total_delta_WA; // Compute the LCG state after q full cycles using the computed matrix M_lambda_q. // x_{mu + q*lambda} = A' * x_mu + B' where M_lambda_q = {{A', B'}, {0, 1}}. uint32 A_prime = M_lambda_q.mat[0][0]; uint32 B_prime = M_lambda_q.mat[0][1]; // Need uint64 intermediate calculation for A' * x_mu + B' to avoid overflow before modulo 2^32. current_x = (uint32)((uint64)A_prime * x_mu + B_prime); // Simulate the remaining r steps. for (uint64 i = 0; i < r; ++i) { // Update LCG state first for turn k = mu + q*lambda + i + 1. current_x = a * current_x + b; uint32 roll = (current_x % 6) + 1; // Determine whose turn based on absolute turn index. uint64 current_turn_idx = mu + q * lambda + i + 1; if (current_turn_idx % 2 != 0) { // Takahashi's turn P_T += roll; if (P_T % 2 != 0) B_T++; else W_T++; } else { // Aoki's turn P_A += roll; if (P_A % 2 != 0) B_A++; else W_A++; } } } // If lambda=0 (no cycle found within total_turns) or remaining_turns=0, // the simulation is effectively complete after the mu steps. No further action needed in this block. // Calculate final scores: minimum of black and white stones for each player. uint64 score_T = std::min(B_T, W_T); uint64 score_A = std::min(B_A, W_A); // Output the scores. std::cout << score_T << " " << score_A << "\n"; return 0; }