結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0