Submission #7570138
Source Code Expand
#include <bits/stdc++.h> using namespace std; namespace FastFourierTransform { using C = complex< double >; void DiscreteFourierTransform(vector<C> &F, bool rev) { const int N = (int)F.size(); const double PI = (rev ? -1 : 1) * acos(-1); for (int i = 0, j = 1; j + 1 < N; ++j) { for (int k = N >> 1; k > (i ^= k); k >>= 1); if (i > j) swap(F[i], F[j]); } C w, s, t; for (int i = 1; i < N; i <<= 1) { for (int k = 0; k < i; ++k) { w = polar(1.0, PI / i * k); for (int j = 0; j < N; j += i * 2) { s = F[j + k]; t = C( F[j + k + i].real() * w.real() - F[j + k + i].imag() * w.imag(), F[j + k + i].real() * w.imag() + F[j + k + i].imag() * w.real() ); F[j + k] = s + t, F[j + k + i] = s - t; } } } if (rev) for (int i = 0; i < N; ++i) F[i] /= N; } vector<long long> Multiply(const vector<int> &A, const vector<int> &B) { int sz = 1; while (sz < A.size() + B.size() - 1) sz <<= 1; vector<C> F(sz), G(sz); for (int i = 0; i < A.size(); ++i) F[i] = A[i]; for (int i = 0; i < B.size(); ++i) G[i] = B[i]; DiscreteFourierTransform(F, false); DiscreteFourierTransform(G, false); for (int i = 0; i < sz; ++i) F[i] *= G[i]; DiscreteFourierTransform(F, true); vector<long long> X(A.size() + B.size() - 1); for (int i = 0; i < A.size() + B.size() - 1; ++i) X[i] = F[i].real() + 0.5; return (X); } }; int N; vector<int> A, B; signed main() { cin >> N; A.resize(N + 1); B.resize(N + 1); for (int i = 1; i <= N; ++i) cin >> A[i] >> B[i]; auto C = FastFourierTransform::Multiply(A, B); for (int i = 1; i <= 2 * N; ++i) { cout << C[i] << endl; } }
Submission Info
Submission Time | |
---|---|
Task | C - 高速フーリエ変換 |
User | morio__ |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2036 Byte |
Status | AC |
Exec Time | 459 ms |
Memory | 10752 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01 |
All | 00_sample_01, 01_00_01, 01_01_19, 01_02_31, 01_03_22, 01_04_31, 01_05_40, 01_06_15, 01_07_39, 01_08_28, 01_09_30, 01_10_23, 01_11_33, 01_12_11, 01_13_28, 01_14_41, 01_15_26, 01_16_49, 01_17_34, 01_18_02, 01_19_33, 01_20_29, 02_00_51254, 02_01_82431, 02_02_17056, 02_03_34866, 02_04_6779, 02_05_65534, 02_06_65535, 02_07_65536, 02_08_65537, 02_09_65538, 02_10_100000 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01 | AC | 14 ms | 512 KB |
01_00_01 | AC | 1 ms | 256 KB |
01_01_19 | AC | 1 ms | 256 KB |
01_02_31 | AC | 1 ms | 256 KB |
01_03_22 | AC | 1 ms | 256 KB |
01_04_31 | AC | 1 ms | 256 KB |
01_05_40 | AC | 1 ms | 256 KB |
01_06_15 | AC | 1 ms | 256 KB |
01_07_39 | AC | 1 ms | 256 KB |
01_08_28 | AC | 1 ms | 256 KB |
01_09_30 | AC | 1 ms | 256 KB |
01_10_23 | AC | 1 ms | 256 KB |
01_11_33 | AC | 1 ms | 256 KB |
01_12_11 | AC | 1 ms | 256 KB |
01_13_28 | AC | 1 ms | 256 KB |
01_14_41 | AC | 1 ms | 256 KB |
01_15_26 | AC | 1 ms | 256 KB |
01_16_49 | AC | 1 ms | 256 KB |
01_17_34 | AC | 1 ms | 256 KB |
01_18_02 | AC | 1 ms | 256 KB |
01_19_33 | AC | 1 ms | 256 KB |
01_20_29 | AC | 1 ms | 256 KB |
02_00_51254 | AC | 237 ms | 5504 KB |
02_01_82431 | AC | 393 ms | 10368 KB |
02_02_17056 | AC | 84 ms | 2688 KB |
02_03_34866 | AC | 174 ms | 5120 KB |
02_04_6779 | AC | 29 ms | 896 KB |
02_05_65534 | AC | 281 ms | 5888 KB |
02_06_65535 | AC | 280 ms | 5888 KB |
02_07_65536 | AC | 341 ms | 9984 KB |
02_08_65537 | AC | 341 ms | 9984 KB |
02_09_65538 | AC | 342 ms | 9984 KB |
02_10_100000 | AC | 459 ms | 10752 KB |