把1、2和3、4的藏钱地方的钱的和的可能枚举出来，原始的O(n^2)会tle，用fft。
然后暴力枚举query的值，拆成两半，把两部分的和乘起来。
1 #include2 using namespace std; 3 4 typedef long long LL; 5 const double PI = acos(-1.0); 6 typedef struct Complex { 7 double r,i; 8 Complex(double _r = 0.0,double _i = 0.0) { 9 r = _r; i = _i; 10 } 11 Complex operator +(const Complex &b) { 12 return Complex(r+b.r,i+b.i); 13 } 14 Complex operator -(const Complex &b) { 15 return Complex(r-b.r,i-b.i); 16 } 17 Complex operator *(const Complex &b) { 18 return Complex(r*b.r-i*b.i,r*b.i+i*b.r); 19 } 20 }Complex; 21 void change(Complex y[],LL len) { 22 LL i,j,k; 23 for(i = 1, j = len/2;i < len-1; i++) { 24 if(i < j)swap(y[i],y[j]); 25 k = len/2; 26 while( j >= k) { 27 j -= k; 28 k /= 2; 29 } 30 if(j < k) j += k; 31 } 32 } 33 34 void fft(Complex y[],LL len,LL on) { 35 change(y,len); 36 for(LL h = 2; h <= len; h <<= 1) { 37 Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); 38 for(LL j = 0;j < len;j+=h) { 39 Complex w(1,0); 40 for(LL k = j;k < j+h/2;k++) { 41 Complex u = y[k]; 42 Complex t = w*y[k+h/2]; 43 y[k] = u+t; 44 y[k+h/2] = u-t; 45 w = w*wn; 46 } 47 } 48 } 49 if(on == -1) { 50 for(LL i = 0;i < len;i++) { 51 y[i].r /= len; 52 } 53 } 54 } 55 56 const LL maxn = 69200; 57 LL cnt[5][maxn]; 58 Complex f[5][maxn]; 59 Complex r[3][maxn]; 60 LL rx[3][maxn]; 61 LL n, len, mx; 62 63 void gao(LL i1, LL i2, LL id) { 64 for(LL i = 0; i < len; i++) f[i1][i] = Complex(0, 0); 65 for(LL i = 0; i < mx; i++) f[i1][i] = Complex(cnt[i1][i], 0); 66 fft(f[i1], len, 1); 67 for(LL i = 0; i < len; i++) f[i2][i] = Complex(0, 0); 68 for(LL i = 0; i < mx; i++) f[i2][i] = Complex(cnt[i2][i], 0); 69 fft(f[i2], len, 1); 70 for(LL i = 0; i < len; i++) r[id][i] = f[i1][i] * f[i2][i]; 71 fft(r[id], len, -1); 72 for(LL i = 0; i < len; i++) rx[id][i] = (LL)(r[id][i].r + 0.5); 73 } 74 75 int main() { 76 // freopen("in", "r", stdin); 77 int T, q; 78 LL x; 79 scanf("%d", &T); 80 while(T--) { 81 memset(cnt, 0, sizeof(cnt)); 82 scanf("%lld",&n); 83 mx = 0; 84 for(LL i = 1; i <= 4; i++) { 85 for(LL j = 1; j <= n; j++) { 86 scanf("%lld", &x); 87 mx = max(mx, x); 88 cnt[i][x]++; 89 } 90 } 91 mx++; len = 1; 92 while(len < 2 * mx) len <<= 1; 93 gao(1, 2, 0); gao(3, 4, 1); 94 scanf("%d", &q); 95 while(q--) { 96 LL val; 97 scanf("%lld", &val); 98 LL ret = 0; 99 for(LL i = 0; i <= val; i++) {100 LL l = i, r = val - i;101 ret += rx[0][l] * rx[1][r];102 // cout << l << "->" << rx[0][l] << " " << r << "->" << rx[1][r] << endl;103 }104 printf("%lld\n", ret);105 }106 }107 return 0;108 }