結果

問題 No.434 占い
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:20:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 112 ms / 2,000 ms
コード長 2,258 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 82,624 KB
実行使用メモリ 88,596 KB
最終ジャッジ日時 2025-04-24 12:22:12
合計ジャッジ時間 3,481 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    
    max_n = 10**5
    fact = [1] * (max_n + 1)
    count_3 = [0] * (max_n + 1)
    
    for x in range(1, max_n + 1):
        m = x
        cnt = 0
        while m % 3 == 0:
            cnt += 1
            m = m // 3
        count_3[x] = count_3[x-1] + cnt
        fact[x] = (fact[x-1] * m) % 9
    
    inv = {1: 1, 2: 5, 4: 7, 5: 2, 7: 4, 8: 8}
    
    for s in cases:
        n = len(s)
        if n == 1:
            print(s)
            continue
        n_minus_1 = n - 1
        total = 0
        for i in range(n):
            d = int(s[i]) % 9
            k = i
            if k > n_minus_1 - k:
                k = n_minus_1 - k  # Use symmetry of combinations
            
            sum_n = count_3[n_minus_1]
            sum_k = count_3[k]
            sum_nk = count_3[n_minus_1 - k]
            e = sum_n - sum_k - sum_nk
            
            if e >= 2:
                mod_val = 0
            elif e == 1:
                numerator = fact[n_minus_1]
                denominator = (fact[k] * fact[n_minus_1 - k]) % 9
                if denominator == 0:
                    mod_val = 0
                else:
                    inv_den = inv.get(denominator, 0)
                    if inv_den == 0:
                        mod_val = 0
                    else:
                        m = (numerator * inv_den) % 9
                        mod_val = (3 * m) % 9
            else:
                numerator = fact[n_minus_1]
                denominator = (fact[k] * fact[n_minus_1 - k]) % 9
                if denominator == 0:
                    mod_val = 0
                else:
                    inv_den = inv.get(denominator, 0)
                    if inv_den == 0:
                        mod_val = 0
                    else:
                        mod_val = (numerator * inv_den) % 9
            
            term = (d * mod_val) % 9
            total += term
        
        total_mod = total % 9
        if total_mod == 0:
            if all(c == '0' for c in s):
                print(0)
            else:
                print(9)
        else:
            print(total_mod)

if __name__ == "__main__":
    main()
0