fork download 
  1. /* Author haleyk10198 */
  2. /* 作者:  haleyk10198 */
  3. /* CF handle: haleyk100198*/
  4. #include <bits/stdc++.h>
  5.  
  6. #define MOD 1000000007
  7. #define LINF (1LL<<60)
  8. #define INF 2147483647
  9. #define PI 3.1415926535897932384626433
  10. #define ll long long
  11. #define pii pair<int,int>
  12. #define mp(x,y) make_pair((x),(y))
  13. #define pb(x) push_back((x))
  14. #define vi vector<int>
  15. #define vvi vector<vi>
  16. #define MAXN 100
  17. #define ld long double
  18. #define op operator
  19.  
  20. using namespace std;
  21.  
  22. string itos(int x){
  23. 	stringstream ss;
  24. 	ss << x;
  25. 	return ss.str();
  26. }
  27.  
  28. struct base {
  29.    typedef ld T; T re, im;
  30.    base() :re(0), im(0) {}
  31.    base(T re) :re(re), im(0) {}
  32.    base(T re, T im) :re(re), im(im) {}
  33.    base op + (const base& o) const { return base(re + o.re, im + o.im); }
  34.    base op - (const base& o) const { return base(re - o.re, im - o.im); }
  35.    base op * (const base& o) const { return base(re * o.re - im * o.im, re * o.im + im * o.re); }
  36.    base op * (ld k) const { return base(re * k, im * k); }
  37.    base conj() const { return base(re, -im); }
  38. };
  39.  
  40. base w[MAXN]; //omega lookup table
  41. int rev[MAXN]; //reverse lookup table
  42.  
  43. void build_rev(int k) {
  44.    static int rk = -1;
  45.    if( k == rk )return ; rk = k;
  46.    for(int i = 1; i < (1<<k); i++) {
  47.        int j = rev[i-1], t = k-1;
  48.        while( t >= 0 && ((j>>t)&1) ) { j ^= 1 << t; --t; }
  49.        if( t >= 0 ) { j ^= 1 << t; --t; }
  50.        rev[i] = j;
  51.    }
  52. }
  53.  
  54. void fft(base *a, int k) {
  55.    build_rev(k); int n = 1 << k;
  56.    for(int i = 0; i < n; i++) if( rev[i] > i ) swap(a[i], a[rev[i]]);
  57.    for(int l = 2, lll = 1; l <= n; l += l, lll += lll) {
  58.        if( w[lll].re == 0 && w[lll].im == 0 ) {
  59.            ld angle = PI / lll;
  60.            base ww( cosl(angle), -sinl(angle) );
  61.            if( lll > 1 ) for(int j = 0; j < lll; ++j) {
  62.                if( j & 1 ) w[lll + j] = w[(lll+j)/2] * ww;
  63.                else w[lll + j] = w[(lll+j)/2];
  64.            } else w[lll] = base(1, 0);
  65.        }
  66.        for(int i = 0; i < n; i += l) 
  67. 	   	 for(int j = 0; j < lll; j++){
  68.            base v = a[i + j], u = a[i + j + lll] * w[lll + j];
  69.            a[i + j] = v + u; a[i + j + lll] = v - u;
  70.        		}
  71.    }
  72. }
  73.  
  74. base a[110];
  75.  
  76. int main(){
  77. 	//freopen("input.txt","r",stdin);
  78. 	//freopen("output.txt","w",stdout);
  79. 	ios_base::sync_with_stdio(false);
  80. 	a[0] = base(0, 0);
  81. 	a[1] = base(0, 0);
  82. 	a[2] = base(4166667, 0);
  83. 	a[3] = base(1, 0);
  84. 	fft(a, 2); 
  85. 	for(int i = 0; i < 4; i++)
  86. 		cout << a[i].re << ' ' << a[i].im << endl;
  87. 	return 0;
  88. }
  89.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin 
Standard input is empty
stdout 
4.16667e+06 0
-4.16667e+06 1
4.16667e+06 0
-4.16667e+06 -1
https://ideone.com/fTBcq5
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!