結果

問題 No.2045 Two Reflections
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-01-07 17:37:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 2,324 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 81,572 KB
実行使用メモリ 85,980 KB
最終ジャッジ日時 2024-01-07 17:37:15
合計ジャッジ時間 3,189 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,460 KB
testcase_01 AC 36 ms
53,460 KB
testcase_02 AC 85 ms
85,980 KB
testcase_03 AC 88 ms
84,236 KB
testcase_04 AC 84 ms
83,712 KB
testcase_05 AC 63 ms
73,608 KB
testcase_06 AC 65 ms
72,740 KB
testcase_07 AC 85 ms
83,516 KB
testcase_08 AC 89 ms
84,548 KB
testcase_09 AC 99 ms
85,128 KB
testcase_10 AC 80 ms
81,260 KB
testcase_11 AC 61 ms
71,008 KB
testcase_12 AC 38 ms
53,460 KB
testcase_13 AC 35 ms
53,460 KB
testcase_14 AC 35 ms
53,460 KB
testcase_15 AC 34 ms
53,460 KB
testcase_16 AC 35 ms
53,460 KB
testcase_17 AC 35 ms
53,460 KB
testcase_18 AC 35 ms
53,460 KB
testcase_19 AC 35 ms
53,460 KB
testcase_20 AC 36 ms
53,460 KB
testcase_21 AC 79 ms
78,428 KB
testcase_22 AC 80 ms
78,812 KB
testcase_23 AC 78 ms
78,684 KB
testcase_24 AC 79 ms
78,684 KB
testcase_25 AC 88 ms
78,812 KB
testcase_26 AC 71 ms
79,324 KB
testcase_27 AC 71 ms
79,452 KB
testcase_28 AC 72 ms
79,324 KB
testcase_29 AC 71 ms
79,580 KB
権限があれば一括ダウンロードができます

ソースコード

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