bzoj 4836: [Lydsy1704月赛]二元运算

题意：

题解：

因为$a_i$和$b_i$的范围都很小，我们可以把每个值的方案数都算出来，然后$O(1)$回答。如果都是$x + y$或$x - y$的话就是裸的fft了，有这个条件我们可以分治来搞，对于当前区间把$a$的左半边和$b$的右半边求出加起来的方案数，把$a$的右半边和$b$的左半边求出减的方案数，全部加起来就好了。

代码：

#include <bits/stdc++.h>
using namespace std;

const double pi = 3.1415926535897932384626;
const int N = 131072;
int T, n, m, bin[N], A[N], B[N], q;
long long ans[N];
struct Complex
{
    double real, imag;
    Complex() {}
    Complex(double real, double imag) : real(real), imag(imag) {}
} a[N], b[N], w[N], c[N];
Complex operator+(Complex x, Complex y) { return Complex(x.real + y.real, x.imag + y.imag); }
Complex operator-(Complex x, Complex y) { return Complex(x.real - y.real, x.imag - y.imag); }
Complex operator*(Complex x, Complex y) { return Complex(x.real * y.real - x.imag * y.imag, x.real * y.imag + x.imag * y.real); }

void bit_reverse(int n, Complex *x)
{
    for (int i = 0, j = 0; i < n; i++)
    {
        if (i > j) swap(x[i], x[j]);
        for (int k = n >> 1; (j ^= k) < k; k >>= 1);
    }
}
void fft(int n, Complex *x, int op)
{
    if (op == -1)
        for (int i = 1; i < n; i++)
            w[i].imag *= -1;
    bit_reverse(n, x);
    for (int i = 2; i <= n; i <<= 1)
    {
        int m = i >> 1;
        for (int j = 0; j < n; j += i)
            for (int k = 0; k < m; k++)
            {
                Complex hh = x[j + m + k] * w[n / i * k];
                x[j + m + k] = x[j + k] - hh;
                x[j + k] = x[j + k] + hh;
            }
    }
    if (op == -1)
        for (int i = 0; i < n; i++)
        {
            w[i].imag *= -1;
            x[i].real /= n;
        }
}
void wk(int l, int r, bool op) // 是否算等于的方案 !!![l,r)
{
    if (l + 1 == r)
    {
        if (op) ans[0] += A[l] * B[l];
        return;
    }
    int md = l + r >> 1;
    wk(l, md, op);
    wk(md, r, op);
    int num = 0;
    if (!op)
    {
        for (int i = l; i < md; i++)
        {
            a[num++] = Complex(A[i], 0);
        }
        num = 0;
        for (int i = md; i < r; i++)
        {
            b[num++] = Complex(B[i], 0);
        }
    }
    else
    {
        for (int i = md; i < r; i++)
        {
            a[num++] = Complex(A[i], 0);
        }
        num = 0;
        for (int i = md - 1; i >= l; i--)
        {
            b[num++] = Complex(B[i], 0);
        }
    }
    for (int i = num; i < (num << 1); i++) a[i] = b[i] = Complex(0, 0);
    num <<= 1;/*
    for (int i = 0; i < num; i++)
        printf("%.0lf ", a[i].real);
    puts("");
    for (int i = 0; i < num; i++)
        printf("%.0lf ", b[i].real);
    puts("");*/
    Complex wn(cos(2 * pi / num), sin(2 * pi / num));
    for (int i = 1; i < num; i++)
        w[i] = w[i - 1] * wn;
    fft(num, a, 1);
    fft(num, b, 1);
    for (int i = 0; i < num; i++)
        c[i] = a[i] * b[i];
    fft(num, c, -1);/*
    for (int i = 0; i < num; i++)
        printf("%lf %lf\n", c[i].real, c[i].imag);
    puts("");*/
    if (!op)
        for (int i = 0; i < num; i++)
            ans[l + md + i] += llround(c[i].real);
    else
        for (int i = 0; i < num; i++)
            ans[i + 1] += llround(c[i].real);
}
int main()
{
    scanf("%d", &T);
    w[0] = Complex(1, 0);/*
    puts("w:");
    for (int i = 0; i < N; i++)
        printf("%lf %lf\n", w[i].real, w[i].imag);
    puts("");*/
    while (T--)
    {
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(ans, 0, sizeof(ans));
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            A[x]++;
        }
        for (int i = 1; i <= m; i++)
        {
            int x;
            scanf("%d", &x);
            B[x]++;
        }
        wk(0, N >> 1, 0);/*
        for (int i = 0; i < N; i++)
            printf("%lld ", ans[i]);
        puts("");*/
        wk(0, N >> 1, 1);/*
        for (int i = 0; i < N; i++)
            printf("%lld ", ans[i]);
        puts("");*/
        while (q--)
        {
            int x;
            scanf("%d", &x);
            printf("%lld\n", ans[x]);
        }
    }
}