結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    max_m = 1300
    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
    
    def get_divisors(K):
        divisors = []
        for i in range(1, int(K**0.5) + 1):
            if K % i == 0:
                divisors.append(i)
                if i != K // i:
                    divisors.append(K // i)
        divisors = list(sorted(divisors))
        return divisors
    
    divisors = get_divisors(K)
    
    def compute_phi(d):
        result = d
        temp = d
        i = 2
        while i * i <= temp:
            if temp % i == 0:
                while temp % i == 0:
                    temp //= i
                result -= result // i
            i += 1
        if temp > 1:
            result -= result // temp
        return result
    
    phi_dict = {}
    for d in divisors:
        phi_dict[d] = compute_phi(d)
    
    def multiply_poly(a, b, max_degree):
        res = [0] * (max_degree + 1)
        for i in range(len(a)):
            if a[i] == 0:
                continue
            for j in range(len(b)):
                if i + j > max_degree:
                    break
                res[i + j] = (res[i + j] + a[i] * b[j]) % MOD
        return res
    
    def pow_poly(p, exponent, max_degree):
        result = [1] + [0] * max_degree
        current = p.copy()
        while exponent > 0:
            if exponent % 2 == 1:
                result = multiply_poly(result, current, max_degree)
            current = multiply_poly(current, current, max_degree)
            exponent //= 2
        return result
    
    total = 0
    for d in divisors:
        m = K // d
        if m * d != K:
            continue
        
        group1_count = 0
        group2 = []
        for a in A:
            b = a // d
            if b >= m:
                group1_count += 1
            else:
                group2.append(b)
        
        S = [inv_fact[c] if c <= m else 0 for c in range(m + 1)]
        P1 = pow_poly(S, group1_count, m)
        
        dp = [0] * (m + 1)
        dp[0] = 1
        for b in group2:
            if b == 0:
                continue
            for j in range(m, -1, -1):
                for k in range(1, min(b, j) + 1):
                    dp[j] = (dp[j] + dp[j - k] * inv_fact[k]) % MOD
        
        coeff = 0
        for i in range(m + 1):
            j = m - i
            if j >= 0 and j < len(P1) and i < len(dp):
                coeff = (coeff + P1[j] * dp[i]) % MOD
        
        F = coeff * fact[m] % MOD
        total = (total + phi_dict[d] * F) % MOD
    
    inv_K = pow(K, MOD - 2, MOD)
    ans = total * inv_K % MOD
    print(ans)

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