백준10531 Golf Bot

작성일 | In

문제 링크

  • http://icpc.me/10531

문제 출처

  • 2014 SWERC C번

사용 알고리즘

  • FFT

시간복잡도

  • O(N log N)

풀이

N개의 자연수로 구성된 수열 K가 주어졌을 때, 수열 K의 서로 다른 2개의 숫자를 더해서 Dj를 만들 수 있는지 판별해야 합니다.

수열 K의 각 요소들은 최대 20만이므로 뜬금없지만 20만차 다항식을 만들어봅시다.
수열 K의 요소 중 v가 있다면, v차항의 계수를 1로 지정해봅시다.

위에서 만든 20만차 다항식을 제곱해서 나온 다항식을 보면, 어떤 항의 계수는 0이고, 어떤 항의 계수는 0이 아닙니다.
수열 K의 서로 다른 2개의 숫자를 더해서 v를 만들 수 있다면, v차항의 계수가 0이 아닙니다.
직접 손으로 계산해보면 이유를 알 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <complex>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;

typedef complex<double> cpx;
typedef vector<cpx> vec;

const double PI = 3.14159265358979323846264;

void FFT(vector<cpx> &f, bool inv = false){
	int n = f.size();
	for (int i = 1, j = 0; i < n; ++i){
		int b = n >> 1;
		while (!((j ^= b) & b)) b >>= 1;
		if (i < j) swap(f[i], f[j]);
	}
	for (int k = 1; k < n; k <<= 1){
		double a = (inv ? PI / k : -PI / k);
		cpx w(cos(a), sin(a));
		for (int i = 0; i < n; i += (k << 1)){
			cpx wp(1, 0);
			for (int j = 0; j < k; ++j){
				cpx x = f[i + j], y = f[i + j + k] * wp;
				f[i + j] = x + y;
				f[i + j + k] = x - y;
				wp *= w;
			}
		}
	}
	if (inv){
		for (int i = 0; i < n; ++i)
			f[i] /= n;
	}
}

void mul(vec &p){
	int n = 1;
	while (n <= p.size()) n <<= 1;
	n <<= 1;
	p.resize(n);
	FFT(p);
	for (int i = 0; i < n; i++) p[i] = p[i] * p[i];
	FFT(p, 1);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	vector<cpx> v(202020);
	cin >> n;
	for (int i = 0; i < n; i++){
		int t; cin >> t;
		v[t] = cpx(1, 0);
	}
	v[0] = cpx(1, 0);
	mul(v);
	cin >> m;
	int ans = 0;
	for (int i = 0; i < m; i++){
		int t; cin >> t;
		if (round(v[t].real()) > 0) ans++;
	}
	cout << ans;
}