結果

問題 No.1575 Divisor Function Hard
ユーザー gew1fw
提出日時 2025-06-12 20:47:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,406 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 148,844 KB
最終ジャッジ日時 2025-06-12 20:48:03
合計ジャッジ時間 10,420 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
MOD = 998244353

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    M = int(input[ptr]); ptr +=1
    K = int(input[ptr]); ptr +=1
    P = int(input[ptr]); ptr +=1
    Q = int(input[ptr]); ptr +=1

    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    B = list(map(int, input[ptr:ptr+M]))
    ptr += M
    C = list(map(int, input[ptr:ptr+K]))
    ptr += K
    U = list(map(int, input[ptr:ptr+Q]))
    ptr += Q

    # Precompute cnt_a[i] for all i
    max_a = max(A) if A else 0
    cnt_a = [0] * (max_a + 2)
    for a in A:
        for i in range(1, a + 1):
            cnt_a[i] += 1
    # Compute prefix sums for cnt_a
    for i in range(max_a, 0, -1):
        cnt_a[i] = cnt_a[i] % MOD

    # Precompute S_B[k] and S_C[k] for k from 0 to P
    S_B = [0] * (P + 1)
    S_C = [0] * (P + 1)
    for k in range(P + 1):
        s_b = 0
        for b in B:
            s_b = (s_b + pow(b, k, MOD)) % MOD
        S_B[k] = s_b
        s_c = 0
        for c in C:
            s_c = (s_c + pow(c, k, MOD)) % MOD
        S_C[k] = s_c

    # Precompute binomial coefficients C(P, k)
    fact = [1] * (P + 1)
    inv_fact = [1] * (P + 1)
    for i in range(1, P + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact[P] = pow(fact[P], MOD-2, MOD)
    for i in range(P-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    C = [0] * (P + 1)
    for k in range(P + 1):
        C[k] = fact[P] * inv_fact[k] % MOD * inv_fact[P - k] % MOD

    # Precompute divisors for all numbers up to 1e5
    max_p = max(U) if U else 0
    divisors = [[] for _ in range(max_p + 1)]
    for i in range(1, max_p + 1):
        for j in range(i, max_p + 1, i):
            divisors[j].append(i)

    # Precompute exponents for all possible i up to max_p
    max_i = max_p
    pre_i_pow = [[0] * (P + 1) for _ in range(max_i + 1)]
    for i in range(max_i + 1):
        pre_i_pow[i][0] = 1
        for e in range(1, P + 1):
            pre_i_pow[i][e] = pre_i_pow[i][e-1] * i % MOD

    # Precompute exponents for all possible m up to max_p
    max_m = max_p
    pre_m_pow = [[0] * (P + 1) for _ in range(max_m + 1)]
    for m in range(max_m + 1):
        pre_m_pow[m][0] = 1
        for e in range(1, P + 1):
            pre_m_pow[m][e] = pre_m_pow[m][e-1] * m % MOD

    # Precompute T(m) for all m up to max_m
    T = [0] * (max_m + 1)
    for m in range(max_m + 1):
        total = 0
        for k in range(P + 1):
            e = P - k
            if e > P:
                continue
            term = C[k] * pre_m_pow[m][e] % MOD
            term = term * S_B[e] % MOD
            term = term * S_C[k] % MOD
            total = (total + term) % MOD
        T[m] = total

    # Process each query
    results = []
    for uq in U:
        Uq = uq
        res = 0
        for p in range(1, Uq + 1):
            for i in divisors[p]:
                if i > max_a:
                    continue
                m = p // i
                if m > max_m:
                    continue
                sum_bc = T[m] % MOD
                ipow = pre_i_pow[i][P] % MOD
                sum_p_i = ipow * sum_bc % MOD
                cnt = cnt_a[i] if i <= max_a else 0
                term = sum_p_i * cnt % MOD
                res = (res + term) % MOD
        results.append(res % MOD)
    
    for res in results:
        print(res)

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