글 읽기 - 메모리 초과

lkyxbar 1년 전 0

메모리 초과를 어떻게 해결해야할까요?

import sys
from math import sin, cos, pi
input=sys.stdin.readline
def fft(P, W):
    n=len(P)
    if not ~-n:
        return
    even, odd=P[0::2], P[1::2]
    fft(even, W*W)
    fft(odd, W*W)
    wp=complex(1, 0)
    for i in range(n//2):
        P[i]=even[i]+wp*odd[i]
        P[i+n//2]=even[i]-wp*odd[i]
        wp*=W

def mul(vec1, vec2):
    n=1
    while n<len(vec1)+1 or n<len(vec2)+1:
        n+=n
    n+=n
    vec1+=[0]*(n-len(vec1))
    vec2+=[0]*(n-len(vec2))
    vec3=[0 for _ in range(n)]
    w=complex(cos(2*pi/n), sin(2*pi/n))
    fft(vec1, w)
    fft(vec2, w)
    for i in range(n):
        vec3[i]=vec1[i]*vec2[i]
    fft(vec3, w.conjugate())
    for i in range(n):
        vec3[i]=round((vec3[i]/n).real)
    return vec3
n=int(input())
A=list(map(int, input().split()))
ans=[1]
for i in A:
    ans=mul(ans, [i, 1])
Q=int(input())
for _ in range(Q):
    K=int(input())
    print(ans[n-K]%100003)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리 초과

lkyxbar 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말