Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #2628636

Source Code Expand

Copy
```#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 2018-06-07 10:36:39+0900 C - 高速フーリエ変換 naoya_t C++14 (GCC 5.4.1) 100 4868 Byte AC 758 ms 11612 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01
All 100 / 100 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 1 ms 256 KB
01_00_01 1 ms 256 KB
01_01_19 1 ms 256 KB
01_02_31 1 ms 256 KB
01_03_22 1 ms 256 KB
01_04_31 1 ms 256 KB
01_05_40 1 ms 256 KB
01_06_15 1 ms 256 KB
01_07_39 1 ms 256 KB
01_08_28 1 ms 256 KB
01_09_30 1 ms 256 KB
01_10_23 1 ms 256 KB
01_11_33 1 ms 256 KB
01_12_11 1 ms 256 KB
01_13_28 1 ms 256 KB
01_14_41 1 ms 256 KB
01_15_26 1 ms 256 KB
01_16_49 1 ms 256 KB
01_17_34 1 ms 256 KB
01_18_02 1 ms 256 KB
01_19_33 1 ms 256 KB
01_20_29 1 ms 256 KB
02_00_51254 377 ms 5972 KB
02_01_82431 681 ms 10988 KB
02_02_17056 142 ms 2796 KB
02_03_34866 298 ms 5460 KB
02_04_6779 43 ms 1020 KB
02_05_65534 440 ms 6388 KB
02_06_65535 439 ms 6388 KB
02_07_65536 597 ms 10484 KB
02_08_65537 599 ms 10484 KB
02_09_65538 601 ms 10484 KB
02_10_100000 758 ms 11612 KB