結果

問題 No.2045 Two Reflections
ユーザー LyricalMaestroLyricalMaestro
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
54,332 KB
testcase_01 AC 40 ms
52,896 KB
testcase_02 AC 89 ms
86,200 KB
testcase_03 AC 90 ms
84,404 KB
testcase_04 AC 89 ms
84,268 KB
testcase_05 AC 68 ms
72,964 KB
testcase_06 AC 69 ms
73,960 KB
testcase_07 AC 90 ms
83,992 KB
testcase_08 AC 99 ms
84,768 KB
testcase_09 AC 95 ms
85,400 KB
testcase_10 AC 85 ms
81,884 KB
testcase_11 AC 64 ms
70,328 KB
testcase_12 AC 38 ms
53,212 KB
testcase_13 AC 38 ms
53,688 KB
testcase_14 AC 38 ms
52,780 KB
testcase_15 AC 38 ms
53,332 KB
testcase_16 AC 40 ms
53,148 KB
testcase_17 AC 38 ms
53,484 KB
testcase_18 AC 38 ms
52,804 KB
testcase_19 AC 38 ms
54,140 KB
testcase_20 AC 39 ms
52,788 KB
testcase_21 AC 89 ms
79,380 KB
testcase_22 AC 88 ms
79,400 KB
testcase_23 AC 90 ms
79,248 KB
testcase_24 AC 89 ms
79,216 KB
testcase_25 AC 88 ms
78,904 KB
testcase_26 AC 77 ms
80,096 KB
testcase_27 AC 77 ms
79,872 KB
testcase_28 AC 76 ms
79,756 KB
testcase_29 AC 76 ms
79,924 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