Submission #1135020
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) //cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
#include <complex>
#define EPS 0.5
// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
int len = v.size(); s << "\n";
for (int i = 0; i < len; ++i) {
s << v[i]; if (i < len - 1) s << "\t";
}
s << "\n"; return s;
}
int power_of_2(int m) {
int cnt = 0;
while (m > 0) {
cnt += 1;
m >>= 1;
}
return 1 << cnt;
}
template<typename T>
void extend_vector(vector<T> *x, int m) {
int m_ = (int)(*x).size();
assert (m_ <= m);
vector<T> tmp = *x;
(*x).assign(m, T());
for (int i = 0; i < m_; ++i) {
(*x)[i] = tmp[i];
}
}
typedef complex<double> cd;
typedef vector<cd> vcd;
vcd dft(vcd f, int n) {
if (n == 1) {
return f;
}
vcd f0(n/2), f1(n/2);
rep (i, n/2) {
f0[i] = f[2 * i + 0];
f1[i] = f[2 * i + 1];
}
vcd f0_ = dft(f0, n/2);
vcd f1_ = dft(f1, n/2);
cd zeta(cos(2 * M_PI / n), sin(2 * M_PI / n));
cd pow_zeta(1, 0);
rep (i, n) {
f[i] = (f0_[i % (n/2)] + pow_zeta * f1_[i % (n/2)]);
pow_zeta *= zeta;
}
return f;
}
vcd inverse_dft(vcd f, int n) {
if (n == 1) {
return f;
}
vcd f0(n/2), f1(n/2);
rep (i, n/2) {
f0[i] = f[2 * i + 0];
f1[i] = f[2 * i + 1];
}
vcd f0_ = dft(f0, n/2);
vcd f1_ = dft(f1, n/2);
cd zeta(cos(2 * M_PI / n), -sin(2 * M_PI / n));
cd pow_zeta(1, 0);
rep (i, n) {
f[i] = (f0_[i % (n/2)] + pow_zeta * f1_[i % (n/2)]);
pow_zeta *= zeta;
}
return f;
}
vll solve(vll g, vll h) {
int ng, nh;
ng = (int)g.size();
nh = (int)h.size();
int n = power_of_2(ng + nh + 1);
extend_vector(&g, n);
extend_vector(&h, n);
vcd g_(n), h_(n);
rep (i, n) {
g_[i] = cd(g[i], 0);
}
rep (i, n) {
h_[i] = cd(h[i], 0);
}
vcd gg = dft(g_, n);
vcd hh = dft(h_, n);
debug(gg);
debug(hh);
vcd ff(n);
rep (i, n) {
ff[i] = gg[i] * hh[i];
}
debug(ff);
// vcd f = inverse_dft(ff, n);
vcd f = dft(ff, n);
reverse(all(f));
rep (i, n) {
f[i] /= n;
}
debug(f);
vll ret(ng + nh);
rep (i, ng + nh) {
ret[i] = EPS + f[i].real();
}
return ret;
}
int n;
int n_;
vll a, b;
int main() {
scanf("%d", &n_);
n_ += 1;
a.resize(n_);
b.resize(n_);
a[0] = b[0] = 0;
FOR (i, 1, n_) {
scanf("%lld %lld", &a[i], &b[i]);
}
vll f = solve(a, b);
n_ -= 1;
rep (i, 2 * n_) {
printf("%lld\n", f[i]);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 高速フーリエ変換 |
User |
tspcx |
Language |
C++14 (Clang 3.8.0) |
Score |
100 |
Code Size |
3393 Byte |
Status |
AC |
Exec Time |
761 ms |
Memory |
46900 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 |
2 ms |
384 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 |
369 ms |
23596 KB |
02_01_82431 |
AC |
755 ms |
46664 KB |
02_02_17056 |
AC |
180 ms |
11856 KB |
02_03_34866 |
AC |
364 ms |
23332 KB |
02_04_6779 |
AC |
44 ms |
3248 KB |
02_05_65534 |
AC |
375 ms |
23908 KB |
02_06_65535 |
AC |
746 ms |
46420 KB |
02_07_65536 |
AC |
746 ms |
46420 KB |
02_08_65537 |
AC |
747 ms |
46420 KB |
02_09_65538 |
AC |
752 ms |
46420 KB |
02_10_100000 |
AC |
761 ms |
46900 KB |