結果
問題 | No.2045 Two Reflections |
ユーザー | LyricalMaestro |
提出日時 | 2024-01-07 17:33:49 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,264 bytes |
コンパイル時間 | 246 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 85,980 KB |
最終ジャッジ日時 | 2024-01-07 17:33:53 |
合計ジャッジ時間 | 3,523 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
53,460 KB |
testcase_01 | AC | 35 ms
53,460 KB |
testcase_02 | AC | 83 ms
85,980 KB |
testcase_03 | AC | 89 ms
84,236 KB |
testcase_04 | AC | 87 ms
83,712 KB |
testcase_05 | AC | 68 ms
73,608 KB |
testcase_06 | AC | 63 ms
72,740 KB |
testcase_07 | AC | 85 ms
83,516 KB |
testcase_08 | AC | 87 ms
84,548 KB |
testcase_09 | AC | 88 ms
85,116 KB |
testcase_10 | AC | 80 ms
81,260 KB |
testcase_11 | AC | 59 ms
71,008 KB |
testcase_12 | AC | 36 ms
53,460 KB |
testcase_13 | AC | 35 ms
53,460 KB |
testcase_14 | AC | 35 ms
53,460 KB |
testcase_15 | AC | 35 ms
53,460 KB |
testcase_16 | AC | 35 ms
53,460 KB |
testcase_17 | AC | 36 ms
53,460 KB |
testcase_18 | AC | 35 ms
53,460 KB |
testcase_19 | AC | 35 ms
53,460 KB |
testcase_20 | WA | - |
testcase_21 | AC | 79 ms
78,428 KB |
testcase_22 | AC | 89 ms
78,812 KB |
testcase_23 | AC | 81 ms
78,684 KB |
testcase_24 | AC | 80 ms
78,684 KB |
testcase_25 | AC | 78 ms
78,812 KB |
testcase_26 | AC | 72 ms
79,324 KB |
testcase_27 | AC | 72 ms
79,324 KB |
testcase_28 | AC | 72 ms
79,324 KB |
testcase_29 | AC | 71 ms
79,580 KB |
ソースコード
## 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()