結果
| 問題 |
No.1004 サイコロの実装 (2)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:07:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,678 bytes |
| コンパイル時間 | 739 ms |
| コンパイル使用メモリ | 86,508 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:22 |
| 合計ジャッジ時間 | 2,043 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 35 WA * 3 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <algorithm> // 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<uint32, uint64> 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;
}