結果

問題 No.1318 ABCD quadruplets
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:39:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,221 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,880 KB
実行使用メモリ 66,940 KB
最終ジャッジ日時 2025-06-12 16:40:06
合計ジャッジ時間 4,692 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 10 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

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

    # Precompute F_ab and F_cd
    F_ab = defaultdict(lambda: defaultdict(int))
    for a in range(M + 1):
        for b in range(M + 1):
            x = a + b
            t = a*a + b*b
            F_ab[x][t] += 1

    F_cd = F_ab  # F_cd is the same as F_ab

    # Compute convolution
    cnt = defaultdict(lambda: defaultdict(int))
    for x1 in F_ab:
        for t1 in F_ab[x1]:
            count1 = F_ab[x1][t1]
            for x2 in F_cd:
                for t2 in F_cd[x2]:
                    count2 = F_cd[x2][t2]
                    x = x1 + x2
                    t = t1 + t2
                    cnt[x][t] += count1 * count2

    # Compute the result
    result = [0] * (N + 1)
    for n in range(N + 1):
        total = 0
        max_S = int((2 * n) ** 0.5)
        for S in range(0, max_S + 1):
            T = 2 * n - S * S
            if T < 0:
                continue
            if S in cnt and T in cnt[S]:
                total += cnt[S][T]
        result[n] = total

    for res in result:
        print(res)
    print()  # Ensure a newline at the end

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