fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(v) v.begin(), v.end()
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef complex<double> base;
  7. typedef vector<base> poly;
  8. const double PI = acos(-1);
  9.  
  10. void fft(poly &f, bool inv = 0){
  11.     int n = f.size(), j = 0;
  12.     vector<base> root(n >> 1);
  13.     for(int i=1; i<n; i++){
  14.         int bit = (n >> 1);
  15.         while(j >= bit){
  16.             j -= bit; bit >>= 1;
  17.         }
  18.         j += bit;
  19.         if(i < j) swap(f[i], f[j]);
  20.     }
  21.     double ang = 2 * PI / n; if(inv) ang *= -1;
  22.     for(int i=0; i<(n >> 1); i++) root[i] = base(cos(ang*i), sin(ang*i));
  23.     for(int i=2; i<=n; i<<=1){
  24.         int step = n / i;
  25.         for(int j=0; j<n; j+=i){
  26.             for(int k=0; k<(i >> 1); k++){
  27.                 base u = f[j | k], v = f[j | k | i >> 1] * root[step * k];
  28.                 f[j | k] = u + v;
  29.                 f[j | k | i >> 1] = u - v;
  30.             }
  31.         }
  32.     }
  33.     if(inv) for(int i=0; i<n; i++) f[i] /= n;
  34. }
  35.  
  36. vector<ll> multiply_mod(vector<ll> &_a, vector<ll> &_b, ll mod){
  37.     int n = 2;
  38.     while(n < _a.size() + _b.size()) n <<= 1;
  39.     poly a1(n), a2(n), b1(n), b2(n);
  40.     for(int i=0; i<_a.size(); i++){
  41.         a1[i] = _a[i] & 32767;
  42.         a2[i] = _a[i] >> 15;
  43.     }
  44.     for(int i=0; i<_b.size(); i++){
  45.         b1[i] = _b[i] & 32767;
  46.         b2[i] = _b[i] >> 15;
  47.     }
  48.     fft(a1); fft(a2); fft(b1); fft(b2);
  49.     poly r1(n), r2(n), r3(n);
  50.     for(int i=0; i<n; i++){
  51.         r1[i] = a1[i] * b1[i];
  52.         r2[i] = a1[i] * b2[i] + a2[i] * b1[i];
  53.         r3[i] = a2[i] * b2[i];
  54.     }
  55.     fft(r1, 1); fft(r2, 1); fft(r3, 1);
  56.     vector<ll> ret(n);
  57.     for(int i=0; i<n; i++){
  58.         ll a = llround(r1[i].real());
  59.         ll b = llround(r2[i].real());
  60.         ll c = llround(r3[i].real());
  61.         a %= mod; b %= mod; c %= mod;
  62.         ret[i] = a + (b << 15) + (c << 30);
  63.         ret[i] %= mod; if(ret[i] < 0) ret[i] += mod;
  64.     }
  65.     return ret;
  66. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/J1ZzNg
language:
C++14 (gcc 8.3)
created:
4 years 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!