Artifact 30aac07db1a49b69289dcfa47ac8a123493d0214:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 46 61 73 74 20 44 69 73 63 72 65 74 .// Fast Discret
0050: 65 20 46 6f 75 72 69 65 72 20 54 72 61 6e 73 66 e Fourier Transf
0060: 6f 72 6d 0a 2f 2f 20 20 20 4f 28 6e 20 6c 6f 67 orm.// O(n log
0070: 20 6e 29 0a 2f 2f 20 20 20 6e 20 6d 75 73 74 20 n).// n must
0080: 62 65 20 61 20 70 6f 77 65 72 20 6f 66 20 32 2e be a power of 2.
0090: 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 .//.// Verified
00a0: 62 79 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 34 33 by.// - SRM 43
00b0: 36 20 4c 56 33 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 6 LV3.//--------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 2d 0a 0a 43 4d 50 20 74 6d 70 5b 36 -----..CMP tmp[6
0100: 35 35 33 36 2a 34 5d 3b 0a 0a 74 65 6d 70 6c 61 5536*4];..templa
0110: 74 65 3c 69 6e 74 20 46 3e 0a 76 6f 69 64 20 66 te<int F>.void f
0120: 66 74 5f 69 6d 70 6c 28 20 43 4d 50 20 61 5b 5d ft_impl( CMP a[]
0130: 2c 20 69 6e 74 20 6e 2c 20 69 6e 74 20 73 74 72 , int n, int str
0140: 69 64 65 20 3d 20 31 20 29 0a 7b 0a 09 69 66 28 ide = 1 ).{..if(
0150: 20 6e 20 3e 20 31 20 29 0a 09 7b 0a 09 09 43 4d n > 1 )..{...CM
0160: 50 20 2a 65 76 3d 61 2c 20 2a 6f 64 3d 61 2b 73 P *ev=a, *od=a+s
0170: 74 72 69 64 65 3b 0a 09 09 69 6e 74 20 73 32 3d tride;...int s2=
0180: 73 74 72 69 64 65 2a 32 2c 20 6e 32 3d 6e 2f 32 stride*2, n2=n/2
0190: 3b 0a 0a 09 09 66 66 74 5f 69 6d 70 6c 3c 46 3e ;....fft_impl<F>
01a0: 28 20 65 76 2c 20 6e 32 2c 20 73 32 20 29 3b 0a ( ev, n2, s2 );.
01b0: 09 09 66 66 74 5f 69 6d 70 6c 3c 46 3e 28 20 6f ..fft_impl<F>( o
01c0: 64 2c 20 6e 32 2c 20 73 32 20 29 3b 0a 0a 09 09 d, n2, s2 );....
01d0: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e for(int i=0; i<n
01e0: 3b 20 2b 2b 69 29 20 74 6d 70 5b 69 5d 20 3d 20 ; ++i) tmp[i] =
01f0: 65 76 5b 73 32 2a 28 69 25 6e 32 29 5d 20 2b 20 ev[s2*(i%n2)] +
0200: 6f 64 5b 73 32 2a 28 69 25 6e 32 29 5d 2a 70 6f od[s2*(i%n2)]*po
0210: 6c 61 72 28 31 2e 30 2c 20 46 2a 32 2a 4d 5f 50 lar(1.0, F*2*M_P
0220: 49 2a 69 2f 6e 29 3b 0a 09 09 66 6f 72 28 69 6e I*i/n);...for(in
0230: 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 2b 2b 69 29 t i=0; i<n; ++i)
0240: 20 61 5b 73 74 72 69 64 65 2a 69 5d 20 3d 20 74 a[stride*i] = t
0250: 6d 70 5b 69 5d 3b 0a 09 7d 0a 7d 0a 0a 76 6f 69 mp[i];..}.}..voi
0260: 64 20 66 66 74 28 20 76 65 63 74 6f 72 3c 43 4d d fft( vector<CM
0270: 50 3e 26 20 61 20 29 0a 7b 0a 09 66 66 74 5f 69 P>& a ).{..fft_i
0280: 6d 70 6c 3c 2b 31 3e 28 26 61 5b 30 5d 2c 20 61 mpl<+1>(&a[0], a
0290: 2e 73 69 7a 65 28 29 29 3b 0a 7d 0a 0a 76 6f 69 .size());.}..voi
02a0: 64 20 69 66 66 74 28 20 76 65 63 74 6f 72 3c 43 d ifft( vector<C
02b0: 4d 50 3e 26 20 61 20 29 0a 7b 0a 09 66 66 74 5f MP>& a ).{..fft_
02c0: 69 6d 70 6c 3c 2d 31 3e 28 26 61 5b 30 5d 2c 20 impl<-1>(&a[0],
02d0: 61 2e 73 69 7a 65 28 29 29 3b 0a 09 66 6f 72 28 a.size());..for(
02e0: 69 6e 74 20 69 3d 30 3b 20 69 3c 61 2e 73 69 7a int i=0; i<a.siz
02f0: 65 28 29 3b 20 2b 2b 69 29 0a 09 09 61 5b 69 5d e(); ++i)...a[i]
0300: 20 2f 3d 20 61 2e 73 69 7a 65 28 29 3b 0a 7d 0a /= a.size();.}.