結果

問題 No.1318 ABCD quadruplets
ユーザー gew1fw
提出日時 2025-06-12 21:33:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,574 bytes
コンパイル時間 642 ms
コンパイル使用メモリ 81,988 KB
実行使用メモリ 63,584 KB
最終ジャッジ日時 2025-06-12 21:34:39
合計ジャッジ時間 4,773 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    N, M = map(int, sys.stdin.readline().split())

    # Precompute count_ab: s_ab and q_ab for pairs (a, b)
    count_ab = defaultdict(lambda: defaultdict(int))
    for a in range(M + 1):
        for b in range(M + 1):
            s = a + b
            q = a**2 + b**2
            count_ab[s][q] += 1

    # Compute the convolution of count_ab with itself
    count = defaultdict(lambda: defaultdict(int))
    # Convert count_ab into a list of (s, q, cnt) for efficient iteration
    ab_list = []
    for s in count_ab:
        for q in count_ab[s]:
            ab_list.append((s, q, count_ab[s][q]))
    
    # Iterate through all pairs of (s1, q1) and (s2, q2)
    len_ab = len(ab_list)
    for i in range(len_ab):
        s1, q1, cnt1 = ab_list[i]
        for j in range(i, len_ab):
            s2, q2, cnt2 = ab_list[j]
            total_s = s1 + s2
            total_q = q1 + q2
            if i == j:
                total_cnt = cnt1 * cnt2
            else:
                total_cnt = cnt1 * cnt2 * 2
            count[total_s][total_q] += total_cnt

    # Now, for each n, compute the sum over s of count[s][2n - s^2]
    result = [0] * (N + 1)
    for s in count:
        s_sq = s * s
        for q in count[s]:
            if (s_sq + q) % 2 != 0:
                continue
            n = (s_sq + q) // 2
            if n > N:
                continue
            result[n] += count[s][q]

    # Print the result
    for n in range(N + 1):
        print(result[n])

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