結果
| 問題 |
No.1881 Everything is the same...
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:12 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,426 bytes |
| コンパイル時間 | 308 ms |
| コンパイル使用メモリ | 82,308 KB |
| 実行使用メモリ | 82,748 KB |
| 最終ジャッジ日時 | 2025-05-14 13:07:18 |
| 合計ジャッジ時間 | 8,698 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 45 WA * 7 |
ソースコード
import sys
import math
# Increase recursion depth if needed, though likely not necessary.
# sys.setrecursionlimit(2000)
MAX_A = 100001 # Max value for A_i is 10^5
# Precompute primes using a sieve up to MAX_A for factorization purposes
is_prime = [True] * MAX_A
is_prime[0] = is_prime[1] = False
primes = []
for p in range(2, MAX_A):
if is_prime[p]:
primes.append(p)
for i in range(p * p, MAX_A, p):
is_prime[i] = False
# Cache for prime factorizations to avoid recomputation
prime_factor_cache = {}
def get_prime_factorization(n):
"""
Computes the prime factorization of n.
Uses a cache and the precomputed list of primes for efficiency.
Returns a dictionary {prime: exponent}.
"""
# Base case for n=1
if n == 1:
return {}
# Check cache
if n in prime_factor_cache:
return prime_factor_cache[n]
factors = {}
temp_n = n
idx = 0
# Trial division using precomputed primes
while idx < len(primes) and primes[idx] * primes[idx] <= temp_n:
p = primes[idx]
if temp_n % p == 0:
count = 0
while temp_n % p == 0:
temp_n //= p
count += 1
factors[p] = count
idx += 1
# If temp_n is still greater than 1 after dividing by small primes,
# it must be a prime itself.
if temp_n > 1:
factors[temp_n] = 1
# Store result in cache before returning
prime_factor_cache[n] = factors
return factors
# Cache for Grundy values of A_i to avoid recomputation
grundy_cache = {}
def calculate_grundy(A):
"""
Calculates the Grundy value for a game associated with integer A.
The game state decomposes into independent games on Sylow p-subgroups
of the multiplicative group (Z/AZ)^x. The Grundy value is the XOR sum
of Grundy values of these subgames.
"""
# Base case for A=1 (trivial group, no moves possible)
if A == 1:
return 0
# Check cache
state_A = A
if state_A in grundy_cache:
return grundy_cache[state_A]
# Step 1: Prime factorization of A
A_factors = get_prime_factorization(A)
# Structure of (Z/AZ)^x is product of (Z/p^k Z)^x for A = product p^k.
# We need the structure of Sylow q-subgroups of (Z/AZ)^x.
# Store exponents {e1, e2, ...} for Sylow q-subgroup G_{A, q} = C_{q^e1} x C_{q^e2} x ...
sylow_q_exponents = {}
# Step 2-4: Analyze structure contribution from each factor (Z/p^k Z)^x
pk_factor_2_k = 0 # exponent k for p=2
if 2 in A_factors:
pk_factor_2_k = A_factors[2]
# Process contributions from odd prime factors p^k of A
for p, k in A_factors.items():
if p == 2: # Handle p=2 factor separately below
continue
# p is an odd prime
# (Z/p^k Z)^x is cyclic of order phi(p^k) = p^(k-1) * (p-1)
if k == 1:
phi_pk = p - 1
else:
phi_pk = (p**(k-1)) * (p-1)
# Prime factorize phi(p^k) to find its Sylow q-subgroups structure
if phi_pk > 1: # phi=1 gives trivial group, contributes nothing
phi_pk_factors = get_prime_factorization(phi_pk)
# Each q^exponent in phi_pk factorization corresponds to a C_{q^exponent} factor
# in the Sylow q-subgroup G_{A, q}
for q, exponent in phi_pk_factors.items():
if q not in sylow_q_exponents:
sylow_q_exponents[q] = []
sylow_q_exponents[q].append(exponent)
# Process contribution from the p=2 factor (Z/2^k Z)^x if A is even
if pk_factor_2_k > 0:
k = pk_factor_2_k
q = 2 # Only Sylow 2-subgroup gets contribution from (Z/2^k Z)^x
if k == 1:
pass # (Z/2Z)^x is trivial group {1}
elif k == 2:
# (Z/4Z)^x is C2. Sylow 2-subgroup is C2. Adds exponent 1.
if q not in sylow_q_exponents:
sylow_q_exponents[q] = []
sylow_q_exponents[q].append(1)
else: # k >= 3
# (Z/2^k Z)^x is C2 x C_{2^(k-2)}. This is a 2-group.
# Adds exponents 1 and k-2 to the Sylow 2-subgroup structure.
if q not in sylow_q_exponents:
sylow_q_exponents[q] = []
sylow_q_exponents[q].append(1)
sylow_q_exponents[q].append(k - 2)
# Step 5-7: Calculate Grundy value for each Sylow q-subgroup and XOR sum
total_grundy = 0
for q, exponents in sylow_q_exponents.items():
# Skip if exponents list is empty (should not happen if q is a key)
if not exponents: continue
# Check if the Sylow q-subgroup G_{A,q} is elementary abelian
# Elementary abelian means it's isomorphic to (C_q)^k_rank, i.e., all exponents are 1.
is_elementary_abelian = True
sum_exponents = 0
for e in exponents:
if e > 1:
is_elementary_abelian = False
sum_exponents += e
# k_rank is the number of cyclic factors in the decomposition of G_{A,q}
k_rank = len(exponents)
# Skip if rank is 0 (trivial subgroup)
if k_rank == 0: continue
# Apply the hypothesis for Grundy value calculation:
# If elementary abelian (C_q)^k_rank : Grundy value is k_rank mod 2
# Otherwise: Grundy value is sum of exponents
if is_elementary_abelian:
grundy_q = k_rank % 2
else:
grundy_q = sum_exponents
# XOR sum the Grundy values of subgames
total_grundy ^= grundy_q
# Cache the result before returning
grundy_cache[state_A] = total_grundy
return total_grundy
# Main part of the solution execution
# Use sys.stdin.readline for potentially faster input reading
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
# Calculate the final XOR sum of Grundy values for all students
final_xor_sum = 0
for val in A:
final_xor_sum ^= calculate_grundy(val)
# Determine the loser based on the final XOR sum (Nim-sum)
# If final_xor_sum is 0, the first player (X) is in a losing position.
# If final_xor_sum > 0, the first player (X) has a winning strategy.
# The problem asks who takes responsibility, which means who loses.
if final_xor_sum == 0:
print("X") # X loses
else:
print("Y") # Y loses