結果
問題 | No.723 2つの数の和 |
ユーザー |
![]() |
提出日時 | 2024-08-23 22:47:58 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,025 bytes |
コンパイル時間 | 348 ms |
コンパイル使用メモリ | 82,536 KB |
実行使用メモリ | 88,836 KB |
最終ジャッジ日時 | 2024-08-23 22:48:02 |
合計ジャッジ時間 | 3,596 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 RE * 18 |
ソースコード
import cmath import math def fft(x): N = len(x) if N <= 1: return x even = fft(x[0::2]) odd = fft(x[1::2]) T = [cmath.exp(-2j * cmath.pi * k / N) * odd[k] for k in range(N // 2)] return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)] def ifft(x): N = len(x) if N <= 1: return x even = ifft(x[0::2]) odd = ifft(x[1::2]) T = [cmath.exp(2j * cmath.pi * k / N) * odd[k] for k in range(N // 2)] return [(even[k] + T[k]) / 2 for k in range(N // 2)] + [(even[k] - T[k]) / 2 for k in range(N // 2)] def convolve(a, b): s = len(a) + len(b) - 1 t = 1 while t < s: t *= 2 a = a + [0] * (t - len(a)) b = b + [0] * (t - len(b)) A = fft(a) B = fft(b) C = [A[i] * B[i] for i in range(t)] c = ifft(C) return [x.real for x in c[:s]] n,x=map(int,input().split()) A=list(map(int,input().split())) f=[0]*(10*5+1) for a in A: f[a]+=1 f=convolve(f,f) print(int(f[x]))