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

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

def powop(vec, k):
    if not k-1:
        return vec
    temp=powop(vec, k>>1)
    if k&1^1:
        return mul(temp, temp)
    return mul(mul(temp, temp), vec)

N, K=map(int, input().split())
a=list(map(int, input().split()))
f=[0]*-~max(a)
for i in a:
    f[i]+=1
ans=powop(f, K)
for i in range(1, max(a)*K+1):
    if ans[i]:
        print(-~i, end=' ')

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

문제

문제

출처

ICPC

틀린 출력을 합니다

lkyxbar 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말