結果
| 問題 |
No.2045 Two Reflections
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:04:06 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 66 ms / 2,000 ms |
| コード長 | 5,853 bytes |
| コンパイル時間 | 173 ms |
| コンパイル使用メモリ | 82,284 KB |
| 実行使用メモリ | 79,480 KB |
| 最終ジャッジ日時 | 2025-05-14 13:05:50 |
| 合計ジャッジ時間 | 2,886 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
import sys
import math
# Set higher recursion depth for safety, although iterative approach is used.
# sys.setrecursionlimit(200000) # Probably not needed with iterative approach
# Use math.gcd for potentially better performance as it's implemented in C.
gcd = math.gcd
# Function to compute least common multiple (LCM) of two numbers.
def lcm(a, b):
# If either number is 0, LCM is 0.
if a == 0 or b == 0:
return 0
# Optimization: LCM with 1 is the other number.
if a == 1: return b
if b == 1: return a
# Calculate LCM using the formula: lcm(a, b) = |a * b| / gcd(a, b)
# Use integer division //
g = gcd(a, b)
# Python's arbitrary precision integers handle large numbers, so a * b won't overflow.
# The form (a // g) * b is sometimes used to potentially keep intermediate numbers smaller,
# but it's not strictly necessary for correctness in Python.
return (a * b) // g
def solve():
# Read input N, p, q
N, p, q = map(int, sys.stdin.readline().split())
# Define the modulus
MOD = 998244353
# Handle special cases where the group generated by R_p and R'_q is small (size 1 or 2)
# Case 1: Both operations are Identity. This happens if p=1 and q=1.
# The group is {Id}, size is 1.
if p == 1 and q == 1:
print(1)
return
# Case 2: One operation is Identity, the other is not.
# If p=1, R_p = Id. The group generated is {Id, R'_q}.
# Since q != 1 (covered by Case 1), R'_q is not Id (requires q > 1, which is true unless N=1,
# but N=1 implies p=1, q=1). Size is 2.
if p == 1:
print(2)
return
# If q=1, R'_q = Id. The group generated is {Id, R_p}.
# Since p != 1 (covered by Case 1), R_p is not Id. Size is 2.
if q == 1:
print(2)
return
# Case 3: The two operations are identical and non-Identity.
# This happens only if p=N and q=N.
# R_p = R_N (reverses 1..N), R'_q = R_N (reverses 1..N).
# The group generated is {Id, R_N}. Size is 2.
# Note: This requires N > 1, otherwise p=1, q=1 falls into Case 1.
# If N > 1, then p=N > 1 and q=N > 1, so R_N is not Identity.
if p == N and q == N:
print(2)
return
# General case: p > 1, q > 1, and R_p != R'_q.
# The group generated by R_p and R'_q is a dihedral group of order 2k,
# where k is the order of the permutation P = R_p * R'_q.
# We need to find k by computing the LCM of cycle lengths of P.
# Function to compute P(i) = R_p(R'_q(i))
def compute_P(i):
# Apply R'_q: Reflects indices in the range [N-q+1, N]
# The reflection maps an index j in the range to (N-q+1) + (N - j).
# Simplified: 2*N - q + 1 - j
i_prime = i
if N - q + 1 <= i <= N:
i_prime = 2 * N - q + 1 - i
# Apply R_p: Reflects indices in the range [1, p]
# The reflection maps an index k in the range to 1 + (p - k).
# Simplified: p + 1 - k
i_final = i_prime
if 1 <= i_prime <= p:
i_final = p + 1 - i_prime
return i_final
# Use a boolean list to keep track of visited indices. Size N+1 for 1-based indexing.
visited = [False] * (N + 1)
# Variable to store the least common multiple (LCM) of cycle lengths found so far. Initialize to 1.
current_lcm = 1
# Iterate through all indices from 1 to N to find cycles
for i in range(1, N + 1):
# If index i has already been visited (part of a previous cycle), skip it.
if not visited[i]:
curr = i
# Use a dictionary to keep track of nodes encountered in the current path trace
# and the step count at which they were first encountered.
path_indices = {}
steps = 0
# Trace the path starting from i until we encounter a node that has been visited before.
while not visited[curr]:
visited[curr] = True # Mark the current node as visited
path_indices[curr] = steps # Record the step count for this node
curr = compute_P(curr) # Move to the next node in the permutation sequence
steps += 1
# After the loop, `curr` is the first node encountered that was already visited.
# We need to check if `curr` was visited during *this* trace run (meaning we found a cycle)
# or if it was visited in a *previous* trace run (meaning this path leads into an existing cycle).
if curr in path_indices:
# `curr` is in path_indices, so it was visited during this trace run. A cycle is found.
# The cycle starts at the node `curr`.
first_occurrence_idx = path_indices[curr] # Step count when `curr` was first visited in this path
cycle_len = steps - first_occurrence_idx # Length of the cycle
# Update the overall LCM with the length of this new cycle.
# A cycle must have length > 0. Check just in case.
if cycle_len > 0:
current_lcm = lcm(current_lcm, cycle_len)
# else: `curr` was not in path_indices. This means it was visited in a previous trace run.
# The path starting from `i` leads into a cycle that has already been processed.
# No new cycle found, so no update to LCM is needed from this path trace.
# The total number of distinct sequences is the size of the group, which is 2 * k.
# k is the order of P, which is the calculated `current_lcm`.
# Compute the final answer modulo MOD.
result = (2 * current_lcm) % MOD
print(result)
# Call the solve function to run the logic
solve()