fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <complex>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. const double PI = acos(-1.0);
  9.  
  10. using Complex = complex<double>;
  11.  
  12. void fft(vector<Complex>& a, bool invert) {
  13.     int n = a.size();
  14.     if (n <= 1) return;
  15.  
  16.     for (int i = 1, j = 0; i < n; i++) {
  17.         int bit = n >> 1;
  18.         for (; j & bit; bit >>= 1) {
  19.             j ^= bit;
  20.         }
  21.         j ^= bit;
  22.         if (i < j) {
  23.             swap(a[i], a[j]);
  24.         }
  25.     }
  26.  
  27.     for (int len = 2; len <= n; len <<= 1) {
  28.         double ang = 2 * PI / len * (invert ? -1 : 1);
  29.         Complex wlen(cos(ang), sin(ang));
  30.         for (int i = 0; i < n; i += len) {
  31.             Complex w(1);
  32.             for (int j = 0; j < len / 2; j++) {
  33.                 Complex u = a[i + j], v = a[i + j + len / 2] * w;
  34.                 a[i + j] = u + v;
  35.                 a[i + j + len / 2] = u - v;
  36.                 w *= wlen;
  37.             }
  38.         }
  39.     }
  40.  
  41.     if (invert) {
  42.         for (Complex& x : a) {
  43.             x /= n;
  44.         }
  45.     }
  46. }
  47.  
  48. int main() {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.  
  52.     int N;
  53.     cin >> N;
  54.  
  55.     const int MAX_VAL = 50000;
  56.     const int OFFSET = 50000;
  57.     const int MAX_SUM = MAX_VAL * 2;
  58.  
  59.     int poly_size = 1;
  60.     while (poly_size <= MAX_SUM + OFFSET) {
  61.         poly_size <<= 1;
  62.     }
  63.  
  64.     vector<Complex> polyA(poly_size, 0);
  65.     vector<Complex> polyB(poly_size, 0);
  66.  
  67.     for (int i = 0; i < N; ++i) {
  68.         int val;
  69.         cin >> val;
  70.         polyA[val + OFFSET] += 1;
  71.     }
  72.  
  73.     for (int i = 0; i < N; ++i) {
  74.         int val;
  75.         cin >> val;
  76.         polyB[val + OFFSET] += 1;
  77.     }
  78.  
  79.     vector<int> vecC(N);
  80.     for (int i = 0; i < N; ++i) {
  81.         cin >> vecC[i];
  82.     }
  83.  
  84.     fft(polyA, false);
  85.     fft(polyB, false);
  86.  
  87.     vector<Complex> poly_res(poly_size);
  88.     for (int i = 0; i < poly_size; i++) {
  89.         poly_res[i] = polyA[i] * polyB[i];
  90.     }
  91.  
  92.     fft(poly_res, true);
  93.  
  94.     long long count = 0;
  95.     for (int i = 0; i < N; ++i) {
  96.         int target_sum = vecC[i] + 2 * OFFSET;
  97.         if (target_sum >= 0 && target_sum < poly_size) {
  98.             count += round(poly_res[target_sum].real());
  99.         }
  100.     }
  101.  
  102.     cout << count << endl;
  103.  
  104.     return 0;
  105. }
Success #stdin #stdout 0.1s 15920KB
comments (?)
stdin
copy 
3
-1 1 1
-1 2 3
2 3 -2
stdout
copy 
4
https://ideone.com/d6vOv2
language:
C++14 (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!