AtCoder Typical Contest 001

Submission #2628636

Source codeソースコード

#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

Task問題 C - 高速フーリエ変換
User nameユーザ名 naoya_t
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 4868 Byte
File nameファイル名
Exec time実行時間 758 ms
Memory usageメモリ使用量 11612 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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