fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define int64_t uint64_t
  4. #define int uint64_t
  5. #define ld double
  6.  
  7. using namespace std;
  8.  
  9. const int logn = 19;
  10. typedef complex<double> ftype;
  11. const int maxn = 1 << logn;
  12. int shift = 13;
  13. int mask = (1 << shift) - 1;
  14.  
  15. ftype w[maxn];
  16. const double pi = acos(-1);
  17.  
  18. template<typename T>
  19. inline void fft(T *in, ftype *out, int n, int k = 1) {
  20.     if(n == 1) {
  21.         *out = *in;
  22.         return;
  23.     }
  24.     n /= 2;
  25.     fft(in, out, n, 2 * k);
  26.     fft(in + k, out + n, n, 2 * k);
  27.     for(int i = 0; i < n; i++) {
  28.         ftype t = w[n + i] * out[i + n];
  29.         out[i + n] = out[i] - t;
  30.         out[i] += t;
  31.     }
  32. }
  33.  
  34. vector<int> mul(vector<int> a, vector<int> b) {
  35.     int n = a.size() + b.size() - 1;
  36.     while(__builtin_popcount(n) != 1) {
  37.         n++;
  38.     }
  39.     a.resize(n);
  40.     b.resize(n);
  41.     ftype A0[maxn], A1[maxn];
  42.     ftype B0[maxn], B1[maxn];
  43.     for(int i = 0; i < n; i++) {
  44.         A0[i] = {a[i] & mask, (a[i] >> shift) & mask};
  45.         A1[i] = {(a[i] >> 2 * shift) & mask, (a[i] >> 3 * shift) & mask};
  46.         B0[i] = {b[i] & mask, (b[i] >> shift) & mask};
  47.         B1[i] = {(b[i] >> 2 * shift) & mask, (b[i] >> 3 * shift) & mask};
  48.     }
  49.     ftype P0[maxn], P1[maxn], Q0[maxn], Q1[maxn];
  50.     fft(A0, P0, n); fft(A1, P1, n);
  51.     fft(B0, Q0, n); fft(B1, Q1, n);
  52.     for(int i = 0; i < n; i++) {
  53.         ftype a0 = (P0[i] + conj(P0[(n - i) % n])) / ftype(2, 0);
  54.         ftype a1 = (P0[i] - conj(P0[(n - i) % n])) / ftype(0, 2);
  55.         ftype a2 = (P1[i] + conj(P1[(n - i) % n])) / ftype(2, 0);
  56.         ftype a3 = (P1[i] - conj(P1[(n - i) % n])) / ftype(0, 2);
  57.  
  58.         ftype b0 = (Q0[i] + conj(Q0[(n - i) % n])) / ftype(2, 0);
  59.         ftype b1 = (Q0[i] - conj(Q0[(n - i) % n])) / ftype(0, 2);
  60.         ftype b2 = (Q1[i] + conj(Q1[(n - i) % n])) / ftype(2, 0);
  61.         ftype b3 = (Q1[i] - conj(Q1[(n - i) % n])) / ftype(0, 2);
  62.  
  63.         A0[i] = (a0 * b3 + a1 * b2 + a2 * b1 + a3 * b0) + ftype(0, 1) * (a0 * b0);
  64.         A1[i] = (a0 * b2 + a1 * b1 + a2 * b0) + ftype(0, 1) * (a0 * b1 + a1 * b0);
  65.     }
  66.     fft(A0, P0, n); fft(A1, P1, n);
  67.     reverse(P0 + 1, P0 + n);
  68.     reverse(P1 + 1, P1 + n);
  69.     for(int i = 0; i < n; i++) {
  70.         int A = llround((ld)imag(P0[i]) / n), B = llround((ld)imag(P1[i]) / n);
  71.         int C = llround((ld)real(P1[i]) / n), D = llround((ld)real(P0[i]) / n);
  72.         a[i] = A + (B << shift) + (C << 2 * shift) + (D << 3 * shift);
  73.     }
  74.     return a;
  75. }
  76.  
  77.  
  78. int pw = 1ULL << 63;
  79. int bpow(int x, int n) {
  80.     return n ? n % 2 ? x * bpow(x, n - 1) : bpow(x * x, n / 2) : 1;
  81. }
  82.  
  83. signed main() {
  84.     //freopen("input.txt", "r", stdin);
  85.     for(int i = 0; i < logn; i++) {
  86.         int cur = 1 << i;
  87.         for(int j = 0; j < cur; j++) {
  88.             w[cur + j] = polar((ld)1, pi * j / cur);
  89.         }
  90.     }
  91.     int n;
  92.     cin >> n;
  93.     int fact[n + 1], rfact[n + 1];
  94.     int rem[n + 1];
  95.     fact[0] = 1;
  96.     rfact[0] = 1;
  97.     rem[0] = 0;
  98.     for(int i = 1; i <= n; i++) {
  99.         int t = i;
  100.         rem[i] = rem[i - 1];
  101.         while(t % 2 == 0) {
  102.             t /= 2;
  103.             rem[i]++;
  104.         }
  105.         fact[i] = fact[i - 1] * t;
  106.         rfact[i] = bpow(fact[i], pw - 1);
  107.     }
  108.     vector<int> in1(n + 1), in2(n + 1);
  109.     for(int i = 0; i <= n; i++) {
  110.         cin >> in1[i];
  111.         in1[i] *= rfact[i];
  112.         in1[i] <<= i - rem[i];
  113.     }
  114.     for(int i = 0; i <= n; i++) {
  115.         cin >> in2[i];
  116.         in2[i] *= rfact[i];
  117.         in2[i] <<= i - rem[i];
  118.     }
  119.     vector<int> res = mul(in1, in2);
  120.     for(int i = 0; i <= n; ++i) {
  121.         int div_by = i - rem[i];
  122.         res[i] = (res[i] >> div_by) * fact[i];
  123.         cout << uint32_t(res[i]) << ' ';
  124.     }
  125.     cout << '\n';
  126.     return 0;
  127. }
  128.  
Runtime error #stdin #stdout 0.03s 23448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FKmhds
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!