Skip to content

Commit 458268d

Browse files
committed
add comment to FFT
1 parent 3b7226d commit 458268d

1 file changed

Lines changed: 6 additions & 7 deletions

File tree

‎Cpp/Math/FFT.h‎

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4,9 +4,8 @@ using Pc = complex<R>;
44

55
void fft(int s, bool type, Pc c[]) {
66
const int N = 1<<s;
7-
Pc *a = new Pc[N];
8-
Pc *b = new Pc[N];
9-
copy_n(c, N, a);
7+
vector<Pc> a(N), b(N);
8+
copy_n(c, N, a.begin());
109
for (int i = 1; i <= s; i++) {
1110
int W = 1<<(s-i); //変更後の幅W
1211
for (int y = 0; y < N/2; y += W) {
@@ -20,12 +19,12 @@ void fft(int s, bool type, Pc c[]) {
2019
}
2120
swap(a, b);
2221
}
23-
copy_n(a, N, c);
24-
delete[] a;
25-
delete[] b;
22+
copy_n(a.begin(), N, c);
2623
}
2724

28-
void multiply(int s, int x[], int y[], ll z[]) { // x*y -> z. x_i, y_i must positive and lower than 2^30
25+
void multiply(int s, int x[], int y[], ll z[]) {
26+
// x*y -> z. x_i, y_i must positive and lower than 2^30
27+
//!!!this code may be overflow!!!
2928
const int N = 1<<s;
3029
Pc *a[3]; Pc *b[3];
3130
for (int fe = 0; fe < 3; fe++) {

0 commit comments

Comments
 (0)