10531번: Golf Bot

https://www.acmicpc.net/problem/10531

FFT를 이용하여 해결한다.
구현은 http://cubelover.tistory.com/19를 참고했다.

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<complex>
using namespace std;
const int sz = 1 << 19;
int n, m, x, r;
complex<double> a[sz] = { 1 };
void FFT(int inv) {
    for (int i = 0; i < sz; i++) {
        int j = 0;
        for (int k = 0; 1 << k < sz; k++) j = j << 1 | i >> k & 1;
        if (i < j) swap(a[i], a[j]);
    }
    for (int i = 1; i < sz; i <<= 1) {
        complex<double> w = polar(1.0, inv * acos(-1) / i);
        for (int j = 0; j < sz; j += i << 1) {
            complex<double> b = 1;
            for (int k = j; k < j + i; k++) {
                complex<double> u = a[k], v = b*a[k + i];
                a[k] = u + v;
                a[k + i] = u - v;
                b *= w;
            }
        }
    }
}
int main() {
    for (scanf("%d", &n); n--;) scanf("%d", &x), a[x] = 1;
    FFT(1);
    for (int i = 0; i < sz; i++) a[i] *= a[i];
    FFT(-1);
    for (int i = 0; i < sz; i++) a[i] /= sz;
    for (scanf("%d", &m); m--;) scanf("%d", &x), r += real(a[x]) >= 0.5;
    printf("%d", r);
    return 0;
}