結果

問題 No.814 ジジ抜き
ユーザー qwewe
提出日時 2025-05-14 13:04:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 88 ms / 3,000 ms
コード長 4,646 bytes
コンパイル時間 683 ms
コンパイル使用メモリ 68,600 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:06:04
合計ジャッジ時間 4,901 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

// Use unsigned long long for integers up to 10^18.
// The maximum value of unsigned long long is approximately 1.8 * 10^19.
typedef unsigned long long ull;

/**
 * @brief Computes the XOR sum of integers from 0 up to N (inclusive).
 * 
 * The function utilizes the pattern of XOR sums based on N modulo 4:
 * G(N) = 0 ^ 1 ^ ... ^ N
 * G(N) = N   if N % 4 == 0
 * G(N) = 1   if N % 4 == 1
 * G(N) = N+1 if N % 4 == 2
 * G(N) = 0   if N % 4 == 3
 * 
 * The formula used for calculating the XOR sum of an arithmetic progression relies on G(S-1).
 * If S=0, S-1 = -1. In unsigned long long, -1 wraps around to ULLONG_MAX.
 * ULLONG_MAX % 4 = (2^64 - 1) % 4 = 3.
 * The function correctly returns G(ULLONG_MAX) = 0, which corresponds to G(-1)=0 needed for the formula.
 * 
 * @param N The upper limit of the range (inclusive).
 * @return The XOR sum 0 ^ 1 ^ ... ^ N.
 */
ull G(ull N) {
    ull rem = N % 4;
    if (rem == 0) return N;
    if (rem == 1) return 1;
    // If rem == 2, the result is N+1.
    // Using N ^ 1 is equivalent to N+1 for N % 4 == 2 and avoids potential overflow
    // if N is ULLONG_MAX - 1 (which is congruent to 2 mod 4).
    if (rem == 2) return N ^ 1; 
    // if rem == 3
    return 0;
}

int main() {
    // Use fast I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N; // Number of players
    std::cin >> N;
    
    ull total_xor_sum = 0; // Initialize the total XOR sum across all players' cards
    
    // Process each player's hand information
    for (int i = 0; i < N; ++i) {
        ull K; // Number of cards player i has
        ull L; // Starting value of the arithmetic progression for player i
        ull D; // The exponent D_i such that the common difference is 2^D_i
        std::cin >> K >> L >> D;
        
        // The cards player i holds are L, L + 2^D, L + 2*2^D, ..., L + (K-1)*2^D.
        // We need to compute the XOR sum of these K values.
        
        // Decompose L into high and low parts based on D:
        // L = L_high * 2^D + L_low, where L_low = L % 2^D
        
        // Calculate L_high = floor(L / 2^D) using bitwise right shift.
        // This effectively divides L by 2^D.
        ull L_high = L >> D;
        
        // Calculate L_low = L % 2^D using bitwise AND with a mask.
        // The mask is (1ULL << D) - 1, which generates a binary number with D ones.
        // This correctly extracts the lower D bits.
        // The constraints state D <= 59, so D < 64. This ensures 1ULL << D does not overflow
        // standard 64-bit unsigned long long and the mask is computed correctly.
        // If D=0, mask = (1ULL << 0) - 1 = 1 - 1 = 0. L & 0 = 0. Correct.
        ull mask = (1ULL << D) - 1; 
        ull L_low = L & mask;

        // The XOR sum computation can be split into contributions from high bits and low bits.
        
        // Contribution from higher bits (positions D and above):
        // This corresponds to the XOR sum of the sequence S, S+1, ..., S+K-1, where S = L_high,
        // then shifted left by D positions.
        // The XOR sum of a range [A, B] is G(B) ^ G(A-1).
        // Here, A = S, B = S+K-1. The sequence is S, S+1, ..., S+K-1.
        ull S = L_high;
        
        // Compute the range bounds for the G function.
        ull S_plus_K_minus_1 = S + K - 1; 
        // S-1 calculation handles S=0 correctly because unsigned wrap-around to ULLONG_MAX
        // results in G(ULLONG_MAX) = 0, which matches G(-1)=0.
        ull S_minus_1 = S - 1; 
        
        // Compute the XOR sum of the sequence S, S+1, ..., S+K-1 using the G function.
        ull xor_sum_S_sequence = G(S_plus_K_minus_1) ^ G(S_minus_1);
        
        // Shift this value left by D bits to get the contribution from the higher bits part.
        // The shift is safe because D <= 59.
        ull contribution_high = xor_sum_S_sequence << D;
        
        // Contribution from lower bits (positions 0 to D-1):
        // Each term L + k*2^D has its lower D bits equal to L_low.
        // The XOR sum of K identical values L_low is L_low if K is odd, and 0 if K is even.
        ull contribution_low = (K % 2 != 0) ? L_low : 0;
        
        // The total XOR sum for player i is the XOR sum of the high and low parts contributions.
        ull player_xor_sum = contribution_high ^ contribution_low;
        
        // Accumulate this player's XOR sum into the overall total XOR sum.
        total_xor_sum ^= player_xor_sum;
    }
    
    // The final total XOR sum is the value x we are looking for.
    std::cout << total_xor_sum << std::endl;
    
    return 0;
}
0