SHARE
TWEET

Untitled

a guest Sep 21st, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define dbg(x) cerr<<#x<<" = "<<x<<endl;
  3. #define dbg_v(v,n) {cerr<<#v<<" = [";for(int III=0;III<=n;III++)cerr<<v[III]<<(III!=n?",":"]\n");}
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define pii pair<int,int>
  8. #define MOD 1000000007
  9. #define zeros(x) x&(x-1)^x
  10. #define fi first
  11. #define se second
  12. #define Nmax 500005
  13. #define cd complex<double>
  14. using namespace std;
  15.  
  16. int rev(int x, int lg){
  17.     int ans = 0;
  18.     for (int i=0;i<lg;i++) if (x & (1<<i)) ans += (1<<(lg-i-1));
  19.     return ans;
  20. }
  21.  
  22. void FFT(vector<cd> &A, bool inv){
  23.     int sz = A.size();
  24.     int lg = 1;
  25.     while (1<<lg < sz) lg++;
  26.     for (int i=0;i<A.size();i++) if (i < rev(i,lg)) swap(A[i],A[rev(i,lg)]);
  27.  
  28.     for (int len = 2;len<=sz;len *= 2){
  29.         double ang = 2 * acos(-1) / len * (inv ? -1 : 1);
  30.         cd d(cos(ang), sin(ang));
  31.         for (int i = 0;i<sz;i+=len){
  32.             cd w(1,0);
  33.             for (int j=0;j<i/2;j++){
  34.                 cd u = A[i+j], v = w * A[i+j+len/2];
  35.                 A[i+j] = u + v;
  36.                 A[i+j+len/2] = u - v;
  37.                 w *= d;
  38.             }
  39.         }
  40.     }
  41.  
  42.     for (int i=0;i<sz && inv;i++) A[i] /= sz;
  43. }
  44.  
  45.  
  46. vector<int> mult(vector<int> A, vector<int> B){
  47.     int sz = A.size() * 2;
  48.     vector<cd> X,Y,Z;
  49.     X.resize(sz); Y.resize(sz),Z.resize(sz);
  50.     for (int i=0;i<A.size();i++) X[i] = (A[i], 0);
  51.     for (int i=0;i<B.size();i++) Y[i] = (B[i], 0);
  52.  
  53.  
  54.     FFT(X, 0); FFT(Y, 0);
  55.     for (int i=0;i<Z.size();i++) Z[i] = X[i] * Y[i];
  56.     FFT(Z, 1);
  57.  
  58.     vector<int> C;
  59.     C.resize(A.size() + B.size() - 1);
  60.     for (int i=0;i<C.size();i++){
  61.         C[i] = Z[i].real() + 0.5;
  62.     }
  63.  
  64.     return C;
  65. }
  66.  
  67.  
  68. int main(){
  69.     ios::sync_with_stdio(false);
  70.    
  71.     return 0;
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top