Submission #2628636
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(var,n) for(int var=0;var<(n);++var)
#define rep1(var,n) for(int var=1;var<=(n);++var)
////
template<class T>
T extgcd(T a, T b, T& x, T& y) {
for (T u=y=1,v=x=0; a; ) {
T q = b / a;
swap(x -= q*u, u);
swap(y -= q*v, v);
swap(b -= q*a, a);
}
return b;
}
inline long long mod_pow(long long x, long long e, long long mod) {
long long v = 1LL;
for ( ; e; e>>=1) {
if (e & 1) v = (v * x) % mod;
x = (x * x) % mod;
}
return v;
}
inline long long mod_inv(long long a, long long mod) {
// return mod_pow(a, mod-2, mod); // slower
long long x, y;
extgcd(a, mod, x, y);
return (mod + x % mod) % mod;
// ax + MODy = 1
// aとmodが互いに素である限り解が存在する
// ax = 1 - MODy
// ax % MOD = 1
// x = 1/a % MOD
}
long long _garner(vector<long long>& xs, vector<long long>& mods) {
int M = xs.size();
vector<long long> coeffs(M, 1), constants(M, 0);
for (int i=0; i<M-1; ++i) {
long long mod_i = mods[i];
// coffs[i] * v + constants[i] == mr[i].val (mod mr[i].first) を解く
long long v = (xs[i] - constants[i] + mod_i) % mod_i;
v = (v * mod_inv(coeffs[i], mod_i)) % mod_i;
for (int j=i+1; j<M; j++) {
long long mod_j = mods[j];
constants[j] = (constants[j] + coeffs[j] * v) % mod_j;
coeffs[j] = (coeffs[j] * mod_i) % mod_j;
}
}
return constants.back();
}
template<typename T>
inline void bit_reverse(vector<T>& a) {
int n = a.size();
int i = 0;
for (int j=1; j<n-1; ++j) {
for (int k = n >> 1; k >(i ^= k); k >>= 1);
if (j < i) swap(a[i], a[j]);
}
}
template<long long mod, long long primitive_root>
class NTT {
public:
long long get_mod() { return mod; }
void _ntt(vector<long long>& a, int sign) {
const int n = a.size();
assert((n ^ (n&-n)) == 0); //n = 2^k
const long long g = primitive_root; // g is primitive root of mod
long long tmp = (mod - 1) * mod_inv(n, mod) % mod; // -1/n
long long h = mod_pow(g, tmp, mod); // ^n√g
if (sign == -1) h = mod_inv(h, mod);
bit_reverse(a);
for (int m=1; m<n; m<<=1) {
const int m2 = 2 * m;
// long long _base = mod_pow(h.val, n/m2, mod);
long long _base = mod_pow(h, n/m2, mod);
long long _w = 1;
for (int x=0; x<m; ++x) {
for (int s=x; s<n; s+=m2) {
long long u = a[s];
long long d = (a[s + m] * _w) % mod;
a[s] = (u+d) % mod;
a[s+m] = (u-d+mod) % mod;
}
_w = (_w * _base) % mod;
}
}
}
void ntt(vector<long long>& input) {
_ntt(input, 1);
}
void intt(vector<long long>& input) {
_ntt(input, -1);
const long long n_inv = mod_inv(input.size(), mod);
for (auto &x : input) x = (x * n_inv) % mod;
}
// 畳み込み演算を行う
vector<long long> convolution(const vector<long long>& a, const vector<long long>& b){
int result_size = a.size() + b.size() - 1;
int n = 1; while (n < result_size) n <<= 1;
vector<long long> _a = a, _b = b;
_a.resize(n, 0);
_b.resize(n, 0);
ntt(_a);
ntt(_b);
for (int i=0; i<n; ++i) _a[i] = (_a[i] * _b[i]) % mod;
intt(_a);
_a.resize(result_size);
return _a;
}
};
vector<long long> convolution_ntt(vector<long long>& a, vector<long long>& b, long long mod=1224736769LL) {
for (auto &x : a) x %= mod;
for (auto &x : b) x %= mod;
// ll maxval = max(a.size(), b.size()) * *max_element(a.begin(), a.end()) * *max_element(b.begin(), b.end());
// if (maxval < 1224736769) {
// NTT<1224736769, 3> ntt3;
// return ntt3.convolution(a, b);
// }
NTT<167772161, 3> ntt1;
NTT<469762049, 3> ntt2;
NTT<1224736769, 3> ntt3;
vector<long long> x1 = ntt1.convolution(a, b);
vector<long long> x2 = ntt2.convolution(a, b);
vector<long long> x3 = ntt3.convolution(a, b);
#ifdef DEBUG
cerr << a << " x " << b << endl;
cerr << "x1:" << x1 << endl;
cerr << "x2:" << x2 << endl;
cerr << "x3:" << x3 << endl;
#endif
vector<long long> ret(x1.size());
vector<long long> mods { 167772161, 469762049, 1224736769, mod };
for (int i=0; i<x1.size(); ++i) {
vector<long long> xs { x1[i], x2[i], x3[i], 0 };
ret[i] = _garner(xs, mods);
}
return ret;
}
int main() {
int N; cin >> N; // 1-100000
vector<ll> g(N+1), h(N+1);
g[0] = h[0] = 0;
rep(i,N){
int A,B; cin >> A >> B;
g[1+i] = A;
h[1+i] = B;
}
vector<ll> f = convolution_ntt(g, h, 1000000007LL);
rep1(k, N*2){
cout << f[k] << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 高速フーリエ変換 |
User |
naoya_t |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
4868 Byte |
Status |
AC |
Exec Time |
758 ms |
Memory |
11612 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 |
1 ms |
256 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 |
377 ms |
5972 KB |
02_01_82431 |
AC |
681 ms |
10988 KB |
02_02_17056 |
AC |
142 ms |
2796 KB |
02_03_34866 |
AC |
298 ms |
5460 KB |
02_04_6779 |
AC |
43 ms |
1020 KB |
02_05_65534 |
AC |
440 ms |
6388 KB |
02_06_65535 |
AC |
439 ms |
6388 KB |
02_07_65536 |
AC |
597 ms |
10484 KB |
02_08_65537 |
AC |
599 ms |
10484 KB |
02_09_65538 |
AC |
601 ms |
10484 KB |
02_10_100000 |
AC |
758 ms |
11612 KB |