2017北理校赛G题人民的名义（FFT）

把1、2和3、4的藏钱地方的钱的和的可能枚举出来，原始的O(n^2)会tle，用fft。
然后暴力枚举query的值，拆成两半，把两部分的和乘起来。
  1 #include <bits/stdc++.h>
  2 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
", ret);
105         }
106     }
107     return 0;
108 }
2017北理校赛G题 人民的名义（FFT）

2017北理校赛G题人民的名义（FFT）
