Submission #5998826
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using int64 = long long;
const int mod = 1e9 + 7;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
os << p.first << " " << p.second;
return os;
}
template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
is >> p.first >> p.second;
return is;
}
template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
for(int i = 0; i < (int) v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
for(T &in : v) is >> in;
return is;
}
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template< typename T = int64 >
vector< T > make_v(size_t a) {
return vector< T >(a);
}
template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}
template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
t = v;
}
template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
for(auto &e : t) fill_v(e, v);
}
namespace FastFourierTransform {
using real=double;
struct C {
real x, y;
C() : x(0), y(0) {}
C(real x, real y) : x(x), y(y) {}
inline C operator+(const C &c) const { return C(x + c.x, y + c.y); }
inline C operator-(const C &c) const { return C(x - c.x, y - c.y); }
inline C operator*(const C &c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); }
inline C conj() const { return C(x, -y); }
};
const real PI = acosl(-1);
int base = 1;
vector< C > rts = {{0, 0},
{1, 0}};
vector< int > rev = {0, 1};
void ensure_base(int nbase) {
if(nbase <= base) return;
rev.resize(1 << nbase);
rts.resize(1 << nbase);
for(int i = 0; i < (1 << nbase); i++) {
rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
}
while(base < nbase) {
real angle = PI * 2.0 / (1 << (base + 1));
for(int i = 1 << (base - 1); i < (1 << base); i++) {
rts[i << 1] = rts[i];
real angle_i = angle * (2 * i + 1 - (1 << base));
rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i));
}
++base;
}
}
void fft(vector< C > &a, int n) {
assert((n & (n - 1)) == 0);
int zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for(int i = 0; i < n; i++) {
if(i < (rev[i] >> shift)) {
swap(a[i], a[rev[i] >> shift]);
}
}
for(int k = 1; k < n; k <<= 1) {
for(int i = 0; i < n; i += 2 * k) {
for(int j = 0; j < k; j++) {
C z = a[i + j + k] * rts[j + k];
a[i + j + k] = a[i + j] - z;
a[i + j] = a[i + j] + z;
}
}
}
}
vector< int64_t > multiply(const vector< int > &a, const vector< int > &b) {
int need = (int) a.size() + (int) b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
ensure_base(nbase);
int sz = 1 << nbase;
vector< C > fa(sz);
for(int i = 0; i < sz; i++) {
int x = (i < (int) a.size() ? a[i] : 0);
int y = (i < (int) b.size() ? b[i] : 0);
fa[i] = C(x, y);
}
fft(fa, sz);
C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0);
for(int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r;
fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r;
fa[i] = z;
}
for(int i = 0; i < (sz >> 1); i++) {
C A0 = (fa[i] + fa[i + (sz >> 1)]) * t;
C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i];
fa[i] = A0 + A1 * s;
}
fft(fa, sz >> 1);
vector< int64_t > ret(need);
for(int i = 0; i < need; i++) {
ret[i] = llround(i & 1 ? fa[i >> 1].y : fa[i >> 1].x);
}
return ret;
}
vector< int > multiply_mod(const vector< int > &a, const vector< int > &b) {
int need = (int) a.size() + (int) b.size() - 1;
int nbase = 0;
while((1 << nbase) < need) nbase++;
ensure_base(nbase);
int sz = 1 << nbase;
vector< C > fa(sz);
for(int i = 0; i < a.size(); i++) {
fa[i] = C(a[i] & ((1 << 15) - 1), a[i] >> 15);
}
fft(fa, sz);
vector< C > fb(sz);
for(int i = 0; i < b.size(); i++) {
fb[i] = C(b[i] & ((1 << 15) - 1), b[i] >> 15);
}
fft(fb, sz);
real ratio = 0.25 / sz;
C r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
for(int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
C a1 = (fa[i] + fa[j].conj());
C a2 = (fa[i] - fa[j].conj()) * r2;
C b1 = (fb[i] + fb[j].conj()) * r3;
C b2 = (fb[i] - fb[j].conj()) * r4;
if(i != j) {
C c1 = (fa[j] + fa[i].conj());
C c2 = (fa[j] - fa[i].conj()) * r2;
C d1 = (fb[j] + fb[i].conj()) * r3;
C d2 = (fb[j] - fb[i].conj()) * r4;
fa[i] = c1 * d1 + c2 * d2 * r5;
fb[i] = c1 * d2 + c2 * d1;
}
fa[j] = a1 * b1 + a2 * b2 * r5;
fb[j] = a1 * b2 + a2 * b1;
}
fft(fa, sz);
fft(fb, sz);
vector< int > ret(need);
for(int i = 0; i < need; i++) {
int64_t aa = llround(fa[i].x);
int64_t bb = llround(fb[i].x);
int64_t cc = llround(fa[i].y);
ret[i] = static_cast< int >((aa + (bb << 15) + (cc << 30)) % mod);
}
return ret;
}
};
int main() {
int N;
cin >> N;
vector< int > A(N + 1), B(N + 1);
for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];
auto C = FastFourierTransform::multiply_mod(A, B);
for(int i = 1; i <= 2 * N; i++) cout << C[i] << "\n";
}
Submission Info
Submission Time |
|
Task |
C - 高速フーリエ変換 |
User |
ei13333 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
6368 Byte |
Status |
AC |
Exec Time |
85 ms |
Memory |
15104 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 |
3 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 |
43 ms |
7680 KB |
02_01_82431 |
AC |
78 ms |
14848 KB |
02_02_17056 |
AC |
19 ms |
3840 KB |
02_03_34866 |
AC |
38 ms |
7424 KB |
02_04_6779 |
AC |
6 ms |
1152 KB |
02_05_65534 |
AC |
48 ms |
7936 KB |
02_06_65535 |
AC |
48 ms |
7936 KB |
02_07_65536 |
AC |
72 ms |
14592 KB |
02_08_65537 |
AC |
72 ms |
14592 KB |
02_09_65538 |
AC |
72 ms |
14592 KB |
02_10_100000 |
AC |
85 ms |
15104 KB |