結果
問題 |
No.1318 ABCD quadruplets
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:42:59 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,574 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 82,072 KB |
実行使用メモリ | 250,564 KB |
最終ジャッジ日時 | 2025-06-12 16:43:03 |
合計ジャッジ時間 | 4,622 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 19 |
ソースコード
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()