結果

問題 No.2959 Dolls' Tea Party
ユーザー gew1fw
提出日時 2025-06-12 16:41:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,384 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 146,340 KB
最終ジャッジ日時 2025-06-12 16:41:38
合計ジャッジ時間 6,201 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

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

def factorize(n):
    factors = {}
    i = 2
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n //= i
        i += 1
    if n > 1:
        factors[n] = 1
    return factors

def get_divisors(factors):
    divisors = [1]
    for p, exp in factors.items():
        temp = []
        for e in range(1, exp + 1):
            pe = p ** e
            for d in divisors:
                temp.append(d * pe)
        divisors += temp
    return sorted(list(set(divisors)))

def compute_phi(divisors, factors):
    phi = {}
    for d in divisors:
        val = d
        for p in factors:
            if d % p == 0:
                val = val // p * (p - 1)
        phi[d] = val
    return phi

def multiply_polynomials(a, b, m):
    res = [0] * (m + 1)
    for i in range(len(a)):
        if a[i] == 0:
            continue
        for j in range(len(b)):
            if i + j > m:
                continue
            res[i + j] = (res[i + j] + a[i] * b[j]) % MOD
    return res

def pow_poly(p, exponent, m):
    result = [1] + [0] * m
    current = p.copy()
    while exponent > 0:
        if exponent % 2 == 1:
            result = multiply_polynomials(result, current, m)
        current = multiply_polynomials(current, current, m)
        exponent = exponent // 2
    return result

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    if K == 0:
        print(0)
        return
    
    factors = factorize(K)
    divisors = get_divisors(factors)
    divisors = [d for d in divisors if K % d == 0]
    divisors = sorted(divisors)
    phi = compute_phi(divisors, factors)
    
    max_m = K
    if K > 0:
        max_m = max(K // min(divisors), 1)
    else:
        max_m = 1
    
    fact = [1] * (max_m + 1)
    for i in range(1, max_m + 1):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact = [1] * (max_m + 1)
    inv_fact[max_m] = pow(fact[max_m], MOD-2, MOD)
    for i in range(max_m-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    total = 0
    for d in divisors:
        m = K // d
        if m == 0:
            continue
        
        cnt_c = {}
        T_count = 0
        for a in A:
            ci = a // d
            ci = min(ci, m)
            if ci >= m:
                T_count += 1
            else:
                if ci not in cnt_c:
                    cnt_c[ci] = 0
                cnt_c[ci] += 1
        
        P = [0] * (m + 1)
        P[0] = 1
        
        for c, count in cnt_c.items():
            if c == 0:
                continue
            max_x = min(c, m)
            G = [inv_fact[x] for x in range(max_x + 1)]
            G_power = pow_poly(G, count, m)
            P = multiply_polynomials(P, G_power, m)
        
        k = T_count
        pow_k = [1] * (m + 1)
        for x in range(1, m + 1):
            pow_k[x] = pow_k[x-1] * k % MOD
        
        Q = [pow_k[x] * inv_fact[x] % MOD for x in range(m + 1)]
        final = multiply_polynomials(P, Q, m)
        coeff = final[m] if m <= len(final)-1 else 0
        f = coeff * fact[m] % MOD
        total = (total + phi[d] * f) % MOD
    
    inv_K = pow(K, MOD-2, MOD)
    ans = total * inv_K % MOD
    print(ans)

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