結果
問題 | No.434 占い |
ユーザー |
![]() |
提出日時 | 2020-03-05 16:28:22 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 386 ms / 2,000 ms |
コード長 | 1,006 bytes |
コンパイル時間 | 92 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 27,392 KB |
最終ジャッジ日時 | 2024-10-14 01:19:08 |
合計ジャッジ時間 | 7,172 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#!/usr/bin/env python3 # %% import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines # %% T = int(readline()) query = readlines() # %% U = 10 ** 5 + 10 fact = [1] * U fact_ord = [0] * U for n in range(1, U): e = 0 m = n while m % 3 == 0: m //= 3 e += 1 fact[n] = fact[n - 1] * m % 9 fact_ord[n] = fact_ord[n - 1] + e fact_inv = [pow(x, 5, 9) for x in fact] # %% def comb_mod_9(n, k): x = fact[n] * fact_inv[k] * fact_inv[n - k] e = fact_ord[n] - fact_ord[k] - fact_ord[n - k] if e >= 2: return 0 elif e == 1: return (3 * x) % 9 else: return x % 9 # %% def solve_query(S): nums = [x - ord('0') for x in S.rstrip()] if all(x == 0 for x in nums): return 0 n = len(nums) - 1 x = sum(comb_mod_9(n, i) * x for i, x in enumerate(nums)) % 9 return x if x else 9 # %% answers = map(solve_query, query) print('\n'.join(map(str, answers)))