글 읽기 - 14882번 다항식과 쿼리 문제 풀이 조언을 구합니다.

bupjae 3년 전 0

이 문제에서는 "정수" 형태의 FFT 가 필요하다는 것을 알게 되었고

문제에서 가능한 쿼리 중 약 1/3 정도는 FFT 의 결과 배열에서 바로 뽑아쓸 수 있는 것으로 보입니다.

그런데, FFT 결과 배열에 없는 나머지 2/3 의 쿼리를 어떻게 해결해야 할지 전혀 감이 잡히질 않고 있습니다.

1) FFT 결과 배열에 없는 나머지 2/3 의 쿼리를 해결할 수 있는 힌트 부탁드립니다.

2) 만약 이 문제가 "정수 FFT" 를 익히는데 너무 어려운 문제라면, BOJ 에 있는 문제 중 좀 더 쉬운 "정수 FFT" 문제의 추천 부탁드립니다.

package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

var in = bufio.NewScanner(os.Stdin)

const (
	mod  = 786433
	n    = 262144
	invn = 786430
)

var nw = [...]int{786432, 100025, 398184, 570203, 417470, 362821, 381732, 212658, 262339, 368266, 778936, 427941, 406601, 83833, 585160, 108788, 213567, 1000}
var iw = [...]int{786432, 686408, 544685, 541396, 462518, 596872, 559977, 331140, 760847, 586330, 444460, 690078, 479839, 294937, 253771, 295516, 430889, 710149}

func nextInt() int {
	in.Scan()
	r := 0
	for _, c := range in.Bytes() {
		r *= 10
		r += int(c - '0')
	}
	return r
}

func main() {
	in.Split(bufio.ScanWords)
	a := make([]int, 262144)
	k := make([]int, 786433)
	for i := range k {
		k[i] = -1
	}
	a[1] = 1
	inplaceFTT(a, false)
	for i, v := range a {
		k[v] = i
	}

	a = make([]int, 262144)
	for i, nn := 0, nextInt(); i <= nn; i++ {
		a[i] = nextInt()
	}
	x0 := a[0]
	inplaceFTT(a, false)
	for m := nextInt(); m > 0; m-- {
		x := nextInt()
		if x == 0 {
			fmt.Println(x0)
		} else if k[x] != -1 {
			fmt.Println(a[k[x]])
		} else {
			fmt.Println("[Need help]")
		}
	}
}

func inplaceFTT(a []int, inv bool) {
	s := uint(bits.UintSize - bits.Len(uint(n)) + 1)
	for i := range a {
		if j := int(bits.Reverse(uint(i)) >> s); i < j {
			a[i], a[j] = a[j], a[i]
		}
	}
	w := nw[:]
	if inv {
		w = iw[:]
	}
	for i, ii := 1, 0; i < n; i, ii = i+i, ii+1 {
		for j := 0; j < n; j += i + i {
			th := 1
			for k := 0; k < i; k++ {
				tmp := a[i+j+k] * th
				tmp %= mod
				a[i+j+k] = (a[j+k] + mod - tmp) % mod
				a[j+k] += tmp
				a[j+k] %= mod
				th *= w[ii]
				th %= mod
			}
		}
	}
	if inv {
		for i := range a {
			a[i] *= invn
			a[i] %= mod
		}
	}
}

sait2000 3년 전 1

FFT는 보통 2개로 나눠서 각각을 처리하고 합치는 설명을 할 텐데 3개로도 나눌 수 있습니다

bupjae 3년 전 0

힌트를 토대로 (inplace 는 아니지만) radix-3 FTT 를 구현, 기존 FTT의 앞단에 붙여서 해결했습니다. 조언 감사합니다.

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

문제

문제

출처

ICPC

14882번 다항식과 쿼리 문제 풀이 조언을 구합니다.

bupjae 3년 전 0

sait2000 3년 전 1

bupjae 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말