AtCoder Typical Contest 001

Submission #2628347

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)

#define DEFAULT_MOD 1000000007LL

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_naive(long long a, long long mod) {
	return mod_pow(a, mod-2, mod);
}

inline long long mod_inv_extgcd(long long a, long long mod) {
	long long x, y;
	extgcd(a, mod, x, y);
	return (mod + x % mod) % mod;
	// ax + MODy = 1
	// x = (1 - MODy)/a = 1/a - MODy/a
}

//#define mod_inv mod_inv_naive
#define mod_inv mod_inv_extgcd


class mint {
public:
	long long val;
	long long mod;
	long long _inv;

public:
	mint()
		: val(0), mod(DEFAULT_MOD), _inv(0) {
			// fprintf(stderr, "mint()\n");
		}
	mint(const mint& m)
		: val(m.val), mod(m.mod), _inv(m._inv) {
			// fprintf(stderr, "mint(m<val=%lld,mod=%lld,_inv=%lld>)\n", val,mod,_inv);
		}
	mint(long long v, long long mod=DEFAULT_MOD, long long inv=0)
		: val((v % mod + mod) % mod), mod(mod), _inv(inv) {
			// fprintf(stderr, "mint(v=%lld, mod=%lld, inv=%lld) -> %lld\n", v,mod,_inv, val);
		}

#ifdef DEBUG
	std::string desc() {
		std::stringstream ss;
		ss << "<" << val << "(mod " << mod << "),inv=" << inv().val << ">";
		return ss.str();
	}
#endif

	mint& set(long long newval) {
		val = (newval % mod + mod) % mod;
		_inv = 0;
		return *this;
	}
	mint& set(mint& b) { // *this = b; return *this;
		val = b.val;
		mod = b.mod;
		_inv = b._inv;
		return *this;
	}

	mint operator+(mint b){ return mint(this->val + b.val, mod); }
	mint operator+(long long v){ return mint(this->val + v, mod); }
	mint& operator+=(mint b){ return set(this->val + b.val); }
	mint& operator+=(long long v){ return set(this->val + v); }

	mint operator-(mint b){ return mint(this->val - b.val, mod); }
	mint operator-(long long v){ return mint(this->val - v, mod); }
	mint& operator-=(mint b){ return set(this->val - b.val); }
	mint& operator-=(long long v){ return set(this->val - v); }

	mint operator*(mint b){ return mint(this->val * b.val, mod); }
	mint operator*(long long v){ return mint(this->val * v, mod); }
	mint& operator*=(mint b){ return set(this->val * b.val); }
	mint& operator*=(long long v){ return set(this->val * v); }

	mint operator-(){ return mint(-this->val, mod); }

	bool operator==(mint b){ return this->val == b.val; }
	bool operator==(long long v){ return this->val == ((v + mod) % mod); }

	bool operator!=(mint b){ return this->val != b.val; }
	bool operator!=(long long v){ return this->val != ((v + mod) % mod); }

	// pow
	mint operator^(long long e){ return mint(mod_pow(this->val, e, mod), mod); }
	mint& operator^=(long long e) { return set(mod_pow(this->val, e, mod)); }

	mint inv() {
		if (_inv == 0) _inv = mod_inv(this->val, mod);
		return mint(_inv, mod);
	}

	// div
	mint operator/(mint b){ return mint(this->val * b.inv().val, mod); }
	mint operator/(long long b){ return mint(this->val * mod_inv(b, mod), mod); }
	mint& operator/=(mint b){ return set(this->val * b.inv().val); }
	mint& operator/=(long long b){ return set(this->val * mod_inv(b, mod)); }
};

std::ostream& operator<<(std::ostream& os, const mint& m){ return ( os << m.val ); }


template <long long MOD>
class Mint : public mint {
public:
	Mint(): mint(0, MOD) {}
	Mint(long long v): mint(v, MOD) {}
};


// #include "ntt.h"
mint garner(vector<mint>& mr, long long mod) {
    int M = mr.size();
    mr.push_back(mint(0, mod));

    vector<mint> coeffs(M+1), constants(M+1);
    for (int i=0; i<M+1; ++i) {
        coeffs[i] = mint(1, mr[i].mod);
        constants[i] = mint(0, mr[i].mod);
    }

    for (int i=0; i<M; ++i) {
		// coffs[i] * v + constants[i] == mr[i].val (mod mr[i].first) を解く
        mint v(mr[i] - constants[i]);
        v /= coeffs[i];

		for (int j=i+1; j<M+1; j++) {
			constants[j] += coeffs[j] * v.val;
			coeffs[j] *= mr[i].mod;
		}
	}

    mr.pop_back();
	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:
    void _ntt(vector<mint>& a, int sign) {
        assert(a[0].mod == mod);

		const int n = a.size();
		assert((n ^ (n&-n)) == 0); //n = 2^k

		const long long g = 3; // g is primitive root of mod

        mint tmp = mint(-1, mod) / n; // tmp = -1/n
        mint h = mint(g, mod) ^ tmp.val; // h = ^n√3

		if (sign == -1) h = h.inv();

        bit_reverse(a);

		for (int m=1; m<n; m<<=1) {
			const int m2 = 2 * m;
			// const ll base = mod_pow(h, n / m2, mod);
            // mint base = h ^ (n/m2);
			// mint w(1, mod);
            long long base = mod_pow(h.val, n/m2, mod);
            long long w = 1;
			for(int x=0; x<m; ++x) {
				for (int s=x; s<n; s+=m2) {
					// mint u = a[s];
					// mint d = a[s + m] * w;
					// a[s] = u + d;
					// a[s + m] = u - d;
					long long u = a[s].val;
					long long d = (a[s + m].val * w) % mod;
					a[s].val = (u + d) % mod;
					a[s + m].val = (u - d + mod) % mod;
                    a[s]._inv = a[s + m]._inv = 0;
				}
				// w *= base;
                w = (w * base) % mod;
			}
		}
	}
	void ntt(vector<mint>& input) {
		_ntt(input, 1);
	}
	void intt(vector<mint>& input) {
		_ntt(input, -1);

        // mint n(input.size(), mod);
		// for (auto &x : input) x *= n.inv(); // = x * n_inv % mod;
        const long long n_inv = mod_inv(input.size(), mod);
		for (auto &x : input) x *= n_inv;
	}

	// 畳み込み演算を行う
	vector<mint> convolution(const vector<long long>& a, const vector<long long>& b){
        int result_size = a.size() + b.size() - 1;
		// int n = pow_2_at_least(result_size);
        int n = 1; while (n < result_size) n <<= 1;

		vector<mint> _a(n, mint(0,mod)), _b(n, mint(0,mod));
        for (int i=0; i<a.size(); ++i) _a[i].val = a[i];
        for (int i=0; i<b.size(); ++i) _b[i].val = b[i];

		ntt(_a);
		ntt(_b);
		for (int i=0; i<n; ++i) _a[i] *= _b[i];
		intt(_a);

        _a.resize(result_size);
		return _a;
	}
};


vector<long long> convolution_ntt_mod(vector<long long>& a, vector<long long>& b, int mod) {
    for (auto &x : a) x %= mod;
    for (auto &x : b) x %= mod;

    NTT<167772161, 3> ntt1;
    NTT<469762049, 3> ntt2;
    NTT<1224736769, 3> ntt3;

    vector<mint> x1 = ntt1.convolution(a, b);
    vector<mint> x2 = ntt2.convolution(a, b);
    vector<mint> 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<mint> mr { x1[0], x2[0], x3[0] };
    for (int i=0; i<x1.size(); ++i) {
        // mr[0] = x1[i];
        // mr[1] = x2[i];
        // mr[2] = x3[i];
        mr[0].set(x1[i].val);
        mr[1].set(x2[i].val);
        mr[2].set(x3[i].val);
		ret[i] = garner(mr, mod).val;
    }

    // ret.resize(a.size() + b.size() - 1);

    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_mod(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ソースコード長 7995 Byte
File nameファイル名
Exec time実行時間 956 ms
Memory usageメモリ使用量 26364 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 2 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 478 ms 13308 KB
02_01_82431 AC 846 ms 26108 KB
02_02_17056 AC 184 ms 6652 KB
02_03_34866 AC 384 ms 13052 KB
02_04_6779 AC 56 ms 1916 KB
02_05_65534 AC 560 ms 13564 KB
02_06_65535 AC 565 ms 13564 KB
02_07_65536 AC 769 ms 25980 KB
02_08_65537 AC 750 ms 25852 KB
02_09_65538 AC 748 ms 25852 KB
02_10_100000 AC 956 ms 26364 KB