글 읽기 - 틀린 출력을 합니다

lkyxbar 1년 전 0

https://www.acmicpc.net/board/...드디어 인1덱1스 에1러 없는 fft코드를 짰습니다! 벗 예제를 넣으면 6입니다 어떻게 된거죠 다항식 곱셈 과정에는 문제가 없다고 생각합니다

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())
k=[int(input()) for _ in range(N)]
f=[0]*-~max(k)
f[0]=1
for i in k:
    f[i]=1
M=int(input())
d=[int(input()) for _ in range(M)]
ans=mul(f, f)
cnt=0
for i in d:
    cnt+=1 if ans[i] else 0
print(cnt)

golazcc83 1년 전 1

42번째 줄에서 ans=mul(f, f)를 사용하셔서 vec1, vec2에 같은 리스트를 파라미터로 주셨는데, 파이썬에서 리스트같은 가변 객체를 파라미터로 주면 call by reference와 같이 동작하기 때문에 22~23번째 줄의 리스트 크기를 맞추는 코드도 사실은 하나의 리스트에 0을 추가하는 것처럼 동작합니다.

ans=mul(f, f) 쪽을 잘 고쳐보시면 될 것 같습니다

lkyxbar 1년 전 0

일단 mul함수는 고치긴 했습니다 근데 이번에는 인덱스 에러가 났습니다

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):
    n=1
    while n<len(vec1)+1:
        n+=n
    n+=n
    vec1+=[0]*(n-len(vec1))
    vec3=[0 for _ in range(n)]
    w=complex(cos(2*pi/n), sin(2*pi/n))
    fft(vec1, w)
    for i in range(n):
        vec3[i]=vec1[i]*vec1[i]
    fft(vec3, w.conjugate())
    for i in range(n):
        vec3[i]=round((vec3[i]/n).real)
    return vec3
N=int(input())
k=[int(input()) for _ in range(N)]
f=[0]*-~max(k)
f[0]=1
for i in k:
    f[i]=1
M=int(input())
d=[int(input()) for _ in range(M)]
cnt=0
ans=mul(f)
for i in d:
    cnt+=1 if ans[i] else 0
print(cnt)

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

문제

문제

출처

ICPC

틀린 출력을 합니다

lkyxbar 1년 전 0

golazcc83 1년 전 1

lkyxbar 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말