結果

問題 No.2045 Two Reflections
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-01-07 17:33:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,264 bytes
コンパイル時間 517 ms
コンパイル使用メモリ 82,088 KB
実行使用メモリ 86,488 KB
最終ジャッジ日時 2024-09-27 19:27:20
合計ジャッジ時間 3,281 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,940 KB
testcase_01 AC 40 ms
53,632 KB
testcase_02 AC 93 ms
86,488 KB
testcase_03 AC 95 ms
84,476 KB
testcase_04 AC 94 ms
84,276 KB
testcase_05 AC 70 ms
72,676 KB
testcase_06 AC 71 ms
73,888 KB
testcase_07 AC 89 ms
84,084 KB
testcase_08 AC 96 ms
84,696 KB
testcase_09 AC 94 ms
85,656 KB
testcase_10 AC 84 ms
81,460 KB
testcase_11 AC 63 ms
70,172 KB
testcase_12 AC 38 ms
53,616 KB
testcase_13 AC 38 ms
53,088 KB
testcase_14 AC 38 ms
53,012 KB
testcase_15 AC 38 ms
53,700 KB
testcase_16 AC 39 ms
54,096 KB
testcase_17 AC 39 ms
54,448 KB
testcase_18 AC 39 ms
53,548 KB
testcase_19 AC 39 ms
52,852 KB
testcase_20 WA -
testcase_21 AC 88 ms
79,456 KB
testcase_22 AC 89 ms
78,932 KB
testcase_23 AC 88 ms
79,252 KB
testcase_24 AC 89 ms
79,304 KB
testcase_25 AC 85 ms
78,888 KB
testcase_26 AC 76 ms
80,048 KB
testcase_27 AC 77 ms
79,708 KB
testcase_28 AC 80 ms
80,088 KB
testcase_29 AC 78 ms
80,136 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

    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