結果

問題 No.2959 Dolls' Tea Party
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:54:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,669 bytes
コンパイル時間 322 ms
コンパイル使用メモリ 82,620 KB
実行使用メモリ 146,412 KB
最終ジャッジ日時 2025-03-31 17:55:53
合計ジャッジ時間 6,381 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def input():
    return sys.stdin.read()

def get_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n//i)
    return sorted(divisors)

def compute_phi_up_to(n):
    phi = list(range(n+1))
    for p in range(2, n+1):
        if phi[p] == p:
            for i in range(p, n+1, p):
                phi[i] -= phi[i] // p
    return phi

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    K = int(data[idx])
    idx +=1
    A = list(map(int, data[idx:idx+N]))
    
    # Precompute factorials and inverse factorials up to K
    max_k = K
    fact = [1]*(max_k+1)
    for i in range(1, max_k+1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1]*(max_k+1)
    inv_fact[max_k] = pow(fact[max_k], MOD-2, MOD)
    for i in range(max_k-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    # Precompute Euler's totient up to K
    max_phi = K
    phi = compute_phi_up_to(max_phi)
    
    divisors = get_divisors(K)
    divisors = list(divisors)
    
    total = 0
    
    for g in divisors:
        c = K // g
        if c ==0:
            continue
        
        # Compute s_i for all A_i and count m and others
        m =0
        freq = {}
        for a in A:
            s = a // c
            if s >= g:
                m +=1
            else:
                if s not in freq:
                    freq[s] =0
                freq[s] +=1
        
        # Compute exponential polynomial for m types
        exp_poly = [0]*(g+1)
        exp_poly[0] =1
        if m >0:
            current =1
            for t in range(1, g+1):
                current = current * m % MOD
                exp_poly[t] = current * inv_fact[t] % MOD
        
        dp = exp_poly.copy()
        
        # Function to multiply two polynomials mod x^(g+1)
        def multiply(a, b):
            res = [0]*(g+1)
            for i in range(g+1):
                if a[i] ==0:
                    continue
                for j in range(g+1 - i):
                    res[i+j] = (res[i+j] + a[i] * b[j]) % MOD
            return res
        
        # Process each group in freq
        for s in freq:
            count = freq[s]
            if count ==0:
                continue
            # Base polynomial is sum_{x=0}^s inv_fact[x] x^t
            base = [0]*(s+1)
            for x in range(s+1):
                base[x] = inv_fact[x]
            # Compute base^count using exponentiation
            result = [1 if i ==0 else 0 for i in range(g+1)]
            power_poly = base[:] + [0]*(g - s)
            exponent = count
            while exponent >0:
                if exponent %2 ==1:
                    result_new = multiply(result, power_poly)
                    # Keep modulo x^(g+1)
                    for i in range(g+1, len(result_new)):
                        pass  # shouldn't happen as multiply is up to g
                    result = result_new[:g+1]
                power_poly_new = multiply(power_poly, power_poly)
                power_poly = power_poly_new[:g+1]
                exponent //=2
            # Multiply result into dp
            dp_new = multiply(dp, result)
            dp = dp_new
        
        ways = dp[g] * fact[g] % MOD
        d = K // g
        if d > max_phi:
            phi_val = compute_phi_up_to(d)[d]
        else:
            phi_val = phi[d]
        total = (total + ways * phi_val) % MOD
    
    # Multiply by inverse(K)
    inv_K = pow(K, MOD-2, MOD)
    ans = (total * inv_K) % MOD
    print(ans)

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