結果

問題 No.2045 Two Reflections
ユーザー LyricalMaestro
提出日時 2024-01-07 17:37:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 2,324 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 86,200 KB
最終ジャッジ日時 2024-09-27 19:27:33
合計ジャッジ時間 3,300 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2045

import math

M0D = 998244353

def main():
    N, p, q = map(int, input().split())
    if p == 1 and q == 1:
        print(1)
        return
    elif p == 1 or q == 1:
        print(2)
        return
    elif p == N and q == N:
        print(2)
        return

    next_nodes = [[(-1, -1) for _ in range(N)] for _ in range(2)]
    # 操作1でできるグラフ
    for i in range(p):
        next_nodes[0][i] = (1, p - 1 - i)
    for i in range(p, N):
        next_nodes[0][i] = (1, i)
    # 操作2でできるグラフ
    for i in reversed(range(N - q, N)):
        next_nodes[1][i] = (0, 2 * N - q - 1 - i)
    for i in reversed(range(N - q)):
        next_nodes[1][i] = (0, i)
    
    # サイクル数を計算
    dists = [[float("inf")] * N for _ in range(2)]
    cycles = []
    for s in range(N):
        if dists[0][s] < float("inf"):
            continue
        
        next_state, next_v = next_nodes[0][s]
        dists[next_state][next_v] = 1
        while next_state != 0 or next_v != s:
            d = dists[next_state][next_v]
            next_state, next_v = next_nodes[next_state][next_v]
            dists[next_state][next_v] = d + 1

        if dists[0][s] > 2:
            cycles.append(dists[0][s])

    # サイクルを素因数分解する
    prime_map = {}
    if len(cycles) > 0:
        max_cycles = max(cycles)
        primes_flags = [ i for i in range(max_cycles + 1) ]
        for p in range(2, max_cycles + 1):
            if p != primes_flags[p]:
                continue
            x = 2 * p
            while x <= max_cycles:
                if primes_flags[x] > p:
                    primes_flags[x] = p
                x += p
    
        # 素因数分解 + 最小公倍数をもとめる
        for c in cycles:
            while c > 1:
                p = primes_flags[c]
                count = 0
                while c % p == 0:
                    c //= p
                    count += 1
                if p not in prime_map:
                    prime_map[p] = 0
                prime_map[p] = max(prime_map[p], count)
    
    # 計算する
    answer = 1
    for p, val in prime_map.items():
        answer *= pow(p, val, M0D)
        answer %= M0D   
    print(answer)            






if __name__ == "__main__":
    main()
0