글 읽기 - 이 문제는 다른 fft를 써야 하나요..?

midori 1년 전 0

이동 (1067), 큰 수 곱셈 3 (22289)과 같은 fft코드를 썼는데 예제 입력마저도 다르게 나옵니다..

fft 코드가 잘못된건가요? 아니면 구현 자체가 잘못된건가요..?

import sys
input = sys.stdin.readline
p = 469762049
def fft(a, inv=False):
    n = len(a)
    j = 0
    for i in range(1,n):
        rev = n >> 1
        while j >= rev:
            j -= rev
            rev >>= 1
        j += rev
        if i < j:
            a[i], a[j] = a[j], a[i]

    step = 2
    while step <= n:
        half = step // 2
        u = pow(3,p//step,p)
        if inv: u = pow(u,p-2,p)
        for i in range(0, n, step):
            w = 1
            for j in range(i, i + half):
                v = a[j + half] * w
                a[j + half] = (a[j] - v)% p
                a[j] += v
                a[j] %= p
                w *= u
                w %= p
        step *= 2

    if inv:
        invn = p - (p-1) // n
        for i in range(n):
            a[i] = (a[i] * invn)%p

def fft_conv(a, b):
    s = len(a) + len(b) - 1
    n = 1 << s.bit_length()
    a += [0 for _ in range(n - len(a))]
    b += [0 for _ in range(n - len(b))]
    fft(a);fft(b)
    for i in range(n):
        a[i] *= b[i]
    fft(a,True)
    return a
    

temp = []
for _ in range(int(input())):
    temp.append(int(input()))

arr = [0]*(max(temp)*2+1)
for i in temp:
    arr[i] = 1
arr[0] = 1

res = fft_conv(arr,arr)

cnt = 0
for _ in range(int(input())):
    if res[int(input())]>0:cnt+=1

print(cnt)

slah007 1년 전 1

일단 질문이 성립이 안됩니다.

문제에 따라 풀이가 달라지고 fft를 어떻게 적용하는지가 달라질 수 있어서 단순히 fft를 썼다로 풀이를 설명할수가 없습니다.

이런 방식으로 식을 세우고 이걸 계산하기 위해 fft를 사용했다는 과정을 설명해 주세요.

midori 1년 전 0

@slah007 죄송합니다. 질문이 처음이라 많이 미흡합니다..

문제에서 요구하는 값(보낼수 있는 경우의 수)을 구하기 위해 다항식(arr) 안에 계수(n) 이 있다면 arr[n] = 1 없다면 arr[n] = 0으로 만들었습니다.

다항식의 제곱 을 계산한 결과(res)를 저장하고

res[i]가 0이라면 보낼 수 없으므로 res[i] > 0인 경우에만 cnt를 1씩 더해주며

결과로 cnt = 문제의 답을 출력하게 코드를 짰습니다.

여기서 arr을 제곱할때 fft로 구현했으나 답이 원하는대로 출력이 되지 않아 질문을 남겼습니다.

slah007 1년 전 1

다시 보니까 제가 말을 좀 세게 한 거 같기도 하네요 그래도 설명을 적어야 읽는 사람이 코드가 확실하게 이해가 되고 답변도 잘 받을 수 있습니다.

제 생각에도 x[i]+x[j]로 나올 수 있는지를 찾으려면 이렇게 x[k[i]]=1로 이루어진 다항식을 제곱하는게 맞는 것 같은데 실수 오차 등의 문제로 보입니다.

res[(int)input()] > 0 대신 (int)res[(int)input()] > 0 등으로 반올림을 하고 다시 실행해 보세요.

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

문제

문제

출처

ICPC

이 문제는 다른 fft를 써야 하나요..?

midori 1년 전 0

slah007 1년 전 1

midori 1년 전 0

slah007 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말