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
AC × 1
AC × 33
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