結果

問題 No.171 スワップ文字列(Med)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:23:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 41 ms / 1,000 ms
コード長 1,735 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 60,096 KB
最終ジャッジ日時 2025-03-20 20:25:02
合計ジャッジ時間 1,230 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import Counter

def count_p_in_factorial(n, p):
    count = 0
    while n > 0:
        n = n // p
        count += n
    return count

def fact_mod(n, p):
    result = 1
    for i in range(1, n + 1):
        current = i
        while current % p == 0:
            current //= p
        result = (result * (current % p)) % p
    return result

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def crt(remainders, primes):
    x = 0
    m = 1
    for a, p in zip(remainders, primes):
        g, p1, q1 = extended_gcd(m, p)
        if (a - x) % g != 0:
            return None
        lcm = m // g * p
        tmp = ((a - x) // g * p1) % (p // g)
        x += m * tmp
        m = lcm
        x %= m
    return x % m

def main():
    S = sys.stdin.readline().strip()
    counts = list(Counter(S).values())
    n = len(S)
    primes = [3, 191]
    crt_data = []
    for p in primes:
        e_n = count_p_in_factorial(n, p)
        e_denominator = 0
        for c in counts:
            e_denominator += count_p_in_factorial(c, p)
        d_p = e_n - e_denominator
        if d_p > 0:
            total_mod = (0 - 1) % p
        else:
            numerator = fact_mod(n, p)
            denominator = 1
            for c in counts:
                d_factor = fact_mod(c, p)
                denominator = (denominator * d_factor) % p
            inv_denominator = pow(denominator, p - 2, p)
            res = (numerator * inv_denominator) % p
            total_mod = (res - 1) % p
        crt_data.append(total_mod)
    result = crt(crt_data, primes)
    print(result)

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