#388489 (C++14) No.754 畳み込みの和

提出ソース

結果

問題	No.754 畳み込みの和
ユーザー	spihill
提出日時	2019-10-11 01:32:41
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	294 ms / 5,000 ms
コード長	7,603 bytes
コンパイル時間	2,018 ms
コンパイル使用メモリ	177,764 KB
実行使用メモリ	16,876 KB
最終ジャッジ日時	2024-11-22 08:13:49
合計ジャッジ時間	3,689 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	283 ms 16,620 KB
testcase_01	AC	283 ms 16,748 KB
testcase_02	AC	294 ms 16,876 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1000000007;

namespace ntt_namespace {
struct NTT_PRIMES {
	int arr[25][2] = {
		{ 998244353,  3}, // 0  : 2^23 * 7 * 17 + 1
		{1811939329, 13}, // 1  : 2^26 * 27 + 1
		{ 469762049,  3}, // 2  : 2^26 * 7 + 1
		{ 167772161,  3}, // 3  : 2^25 * 5 + 1
		{1107296257, 10}, // 4  : 2^25 * 3 * 11 + 1
		{1711276033, 29}, // 5  : 2^25 * 3 * 17 + 1
		{ 754974721,  3}, // 6  : 2^24 * 11 + 1
		{1224736769,  3}, // 7  : 2^24 * 73 + 1
		{ 377487361,  7}, // 8  : 2^23 * 3^2 * 5 + 1
		{ 595591169,  3}, // 9  : 2^23 * 71 + 1
		{ 645922817,  3}, // 10 : 2^23 * 7 * 11 + 1
		{ 985661441,  3}, // 11 : 2^22 * 5 * 47 + 1
		{ 943718401,  7}, // 12 : 2^22 * 3^2 * 5^2 + 1
		{ 935329793,  3}, // 13 : 2^22 * 223 + 1
		{1012924417,  5}, // 14 : 2^21 * 3 * 7 * 23 + 1
		{1004535809,  3}, // 15 : 2^21 * 479 + 1
		{ 975175681, 17}, // 16 : 2^21 * 3 * 5 * 31 + 1
		{ 962592769,  7}, // 17 : 2^21 * 3^3 * 17 + 1
		{ 950009857,  7}, // 18 : 2^21 * 4 * 151 + 1
		{ 924844033,  5}, // 19 : 2^21 * 3^2 * 7^2 + 1
		{1053818881,  7}, // 20 : 2^20 * 3 * 5 * 67 + 1
		{1051721729,  6}, // 21 : 2^20 * 17 * 59 + 1
		{1045430273,  3}, // 22 : 2^20 * 997 + 1
		{1007681537,  3}, // 23 : 2^20 * 31^2 + 1
		{ 976224257,  3}, // 24 : 2^20 * 7^2 * 19 + 1
	};
	constexpr NTT_PRIMES() {}
};
template<int mod, int primitive_root>
struct NTT_ {
	using ll = long long;
	NTT_() {} 
	inline long long mod_pow(long long a, long long p) {
		a %= mod; if (a < 0) a += mod;
		long long res = 1;
		for (; p; p >>= 1, a = a * a % mod) {
			if (p & 1) res = res * a % mod;
		}
		return res;
	}
	inline long long mod_inv(long long a) {
		a = a % mod; if (a < 0) a += mod;
		long long b = mod, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= mod; if (u < 0) u += mod;
		return u;
	}
	inline void bit_reverse(vector<ll>& f) {
		const int n = f.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(f[i], f[j]);
		}
	}
	inline void _ntt(vector<ll>& f, int sign) {
		const int n = f.size();
		ll h = mod_pow(primitive_root, mod_inv(-n));
		if (sign == -1) h = mod_inv(h);
		bit_reverse(f);
		for (int m = 1; m < n; m*= 2) {
			const int m2 = 2 * m;
			const ll base = mod_pow(h, n / m2);
			ll w = 1;
			for (ll x = 0; x < m; x++) {
				for (ll s = x; s < n; s += m2) {
					ll u = f[s];
					ll d = f[s + m] * w % mod;
					f[s] = (u + d) % mod;
					f[s + m] = (u - d + mod) % mod;
				}
				w = w * base % mod;
			}
		}
		for (auto& x : f) if (x < 0) x += mod;
	}
	inline void ntt(vector<ll>& f) {
		_ntt(f, 1);
	}
	inline void intt(vector<ll>& f) {
		_ntt(f, -1);
		const long long n_inv = mod_inv(f.size());
		for (auto& x: f) x = x * n_inv % mod;
	}
	template<class T>
	inline vector<ll> convolution(const vector<T>& f, const vector<T>& g) {
		vector<ll> res;
		convolution(f, g, res);
		return res;
	}
	template<class T>
	inline void convolution(const vector<T>& f, const vector<T>& g, vector<ll>& res) {
		ll sz = 1;
		while (sz < (ll) (f.size() + g.size())) sz *= 2;
		vector<ll> _f(f.begin(), f.end()), _g(g.begin(), g.end());
		_f.resize(sz); _g.resize(sz); res.clear(); res.resize(sz);
		for (auto& x : _f) x %= mod;
		for (auto& x : _g) x %= mod;
		ntt(_f); 
		ntt(_g);
		for (ll i = 0; i < sz; i++) res[i] = _f[i] * _g[i] % mod;
		intt(res);
	}
};
constexpr long long mod_inv(long long a, const int M) {
	long long res = 1;
	for (int p = M - 2; p; p >>= 1, a = a * a % M) {
		if (p & 1) res = res * a % M;
	}
	return res;
}
template<int mod_select>
struct NTT : NTT_<NTT_PRIMES().arr[mod_select][0], NTT_PRIMES().arr[mod_select][1]> {};

template<int mod>
struct ANY_MOD_NTT {
	using ll = long long;
	template<class T, int np1 = 3, int np2 = 8, int np3 = 9>
	inline vector<ll> convolution(const vector<T>& f, const vector<T>& g) {
		vector<ll> res;
		convolution(f, g, res);
		return res;
	}
	template<class T, int np1 = 3, int np2 = 8, int np3 = 9>
	inline void convolution(const vector<T>& f, const vector<T>& g, vector<ll>& res) {
		NTT<np1> ntt1;
		NTT<np2> ntt2;
		NTT<np3> ntt3;
		vector<ll> h1; ntt1.convolution(f, g, h1);
		vector<ll> h2; ntt2.convolution(f, g, h2);
		vector<ll> h3; ntt3.convolution(f, g, h3);
		constexpr ll m1 = NTT_PRIMES().arr[np1][0];
		constexpr ll m2 = NTT_PRIMES().arr[np2][0];
		constexpr ll m3 = NTT_PRIMES().arr[np3][0];
		constexpr ll m1_inv_m2 = mod_inv(m1, m2);
		constexpr ll m12_inv_m3 = mod_inv(m1 * m2 % m3, m3);
		constexpr ll m12_mod = m1 * m2 % mod;
		// ll m1 = NTT_PRIMES().arr[np1][0];
		// ll m2 = NTT_PRIMES().arr[np2][0];
		// ll m3 = NTT_PRIMES().arr[np3][0];
		// ll m1_inv_m2 = mod_inv(m1, m2);
		// ll m12_inv_m3 = mod_inv(m1 * m2 % m3, m3);
		// ll m12_mod = m1 * m2 % mod;
		// static_assert(m1 >= 0);
		// static_assert(m2 >= 0);
		// static_assert(m3 >= 0);
		// static_assert(m1_inv_m2 >= 0);
		// static_assert(m12_inv_m3 >= 0);
		// static_assert(m12_mod >= 0);
		// cout << "1 " << m1 << " " << h1[1] << endl;
		// cout << "2 " << m2 << " " << h2[1] << endl;
		// cout << "3 " << m3 << " " << h3[1] << endl;
		const int sz = h1.size();
		res.clear(); res.resize(sz);
		for (int i = 0; i < sz; i++) {
			ll v1 = (h2[i] - h1[i]) * m1_inv_m2 % m2;
			if (v1 < 0) v1 += m2;
			ll v2 = (h3[i] - (h1[i] + m1 * v1) % m3) * m12_inv_m3 % m3;
			if (v2 < 0) v2 += m3;
			res[i] = (h1[i] + m1 * v1 + m12_mod * v2) % mod;
		}
	}
};
}
using namespace ntt_namespace;

// int f(const vector<long long>& C) {
// 	for (int i = 0; i < (int) C.size(); i++) {
// 		if (C[i] > 1) return i;
// 	}
// 	return -1;
// }

// int main() {
// 	ANY_MOD_NTT<998244353> ntt;
// 	using std::cout;
// 	// NTT<16> ntt;
// 	int N, M; cin >> N >> M;
// 	vector<int> A(1e6+1), B(1e6+1);
// 	vector<long long> C;
// 	map<int, int> ma, mb;
// 	for (int i = 0; i < N; i++) {
// 		int t;
// 		scanf("%d", &t);
// 		A[t]++;
// 		ma[t] = i;
// 	}
// 	for (int i = 0; i < M; i++) {
// 		int t;
// 		scanf("%d", &t);
// 		B[t]++;
// 		mb[t] = i;
// 	}
// 	// auto C = ntt.convolution(A, B);
// 	// using namespace std::chrono;
// 	// steady_clock::time_point begin = steady_clock::now();
// 	ntt.convolution(A, B, C);
// 	// steady_clock::time_point end = steady_clock::now();
// 	// milliseconds elapsed_time = duration_cast<milliseconds>(end - begin);
// 	// cerr << elapsed_time.count() << " ms" << endl;

// 	int r = f(C);
// 	if (r == -1) {
// 		cout << -1 << endl;
// 		return 0;
// 	}
// 	vector<pair<int, int>> res;
// 	for (int i = 0; res.size() < 2; i++) {
// 		if (A[i] && B[r-i]) {
// 			res.emplace_back(ma[i], mb[r-i]);
// 		}
// 	}
// 	cout << res[0].first << " " << res[0].second << " ";
// 	cout << res[1].first << " " << res[1].second << endl;
// }

// int main() {
// 	int N, M;
// 	scanf("%d%d", &N, &M);
// 	vector<int> a(N), b(M);
// 	for (int i = 0; i < N; i++) scanf("%d", &a[i]);
// 	for (int i = 0; i < M; i++) scanf("%d", &b[i]);
// 	ANY_MOD_NTT<998244353> ntt;
// 	auto c = ntt.convolution(a, b);
// 	for (int i = 0; i < N+M-1; i++) {
// 		if (i) cout << " ";
// 		cout << c[i];
// 	}
// 	cout << endl;
// }


signed main() {
	int N;
	cin >> N;
	vector<long long> A(N+1), B(N+1);
	for (int i = 0; i < N + 1; i++) scanf("%lld", &A[i]);
	for (int i = 0; i < N + 1; i++) scanf("%lld", &B[i]);
	ANY_MOD_NTT<MOD> ntt;
	vector<long long> C;
	ntt.convolution<long long, 0, 2, 3>(A, B, C);
	long long res = 0;
	// cout << A[0] << " " << B[0] << " " << A[0] * B[0] % MOD << endl;
	for (int i = 0; i <= N; i++) {
		res += C[i];
		// res %= MOD;
		// cout << res << endl;
	}
	cout << res % MOD << endl;
}

yukicoder

結果

テストケース

ソースコード