結果

問題 No.754 畳み込みの和
ユーザー m1025o1184tm1025o1184t
提出日時 2019-12-20 05:26:13
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 312 ms / 5,000 ms
コード長 2,715 bytes
コンパイル時間 2,002 ms
コンパイル使用メモリ 182,204 KB
実行使用メモリ 11,296 KB
最終ジャッジ日時 2024-07-07 13:50:34
合計ジャッジ時間 3,971 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 312 ms
11,168 KB
testcase_01 AC 306 ms
11,296 KB
testcase_02 AC 309 ms
11,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

template<int mod, int proot>
struct NTT {
	vector<long long>pp, invpp;//memoize proot^(mod-1>>i) and inv
	long long power(long long a, int b)
	{
		long long ret = 1;
		while (b)
		{
			if (b & 1)ret = ret * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return ret;
	}
	void dft(vector<int>& A, bool sign, int id)
	{
		if (id == 0)return;
		int N = 1 << id - 1;
		vector<int>F(N), G(N);
		for (int i = 0; i < N; i++)
		{
			F[i] = A[i << 1];
			G[i] = A[i << 1 | 1];
		}
		dft(F, sign, id - 1);
		dft(G, sign, id - 1);
		long long z = (sign ? invpp : pp)[id], p = 1;
		for (int i = 0; i < N; i++)
		{
			A[i] = (F[i] + p * G[i]) % mod;
			A[i + N] = (F[i] - p * G[i]) % mod;
			if (A[i + N] < 0)A[i + N] += mod;
			(p *= z) %= mod;
		}
	}
	vector<int>multiply(vector<int>A, vector<int>B)
	{
		if (A.empty() || B.empty())
		{
			return(vector<int>){};
		}
		int N = 1, sz = 0;
		vector<int>ret(A.size() + B.size() - 1);
		while (N < ret.size())N <<= 1, sz += 1;
		pp.resize(sz + 1);
		invpp.resize(sz + 1);
		pp[sz] = power(proot, mod - 1 >> sz);
		invpp[sz] = power(pp[sz], mod - 2);
		for (int i = sz - 1; i > 0; i -= 1)
		{
			pp[i] = pp[i + 1] * pp[i + 1] % mod;
			invpp[i] = invpp[i + 1] * invpp[i + 1] % mod;
		}
		A.resize(N);
		B.resize(N);
		dft(A, false, sz);
		dft(B, false, sz);
		for (int i = 0; i < N; i++)A[i] = (long long)A[i] * B[i] % mod;
		dft(A, true, sz);
		long long invN = power(N, mod - 2);
		for (int i = 0; i < ret.size(); i++)ret[i] = invN * A[i] % mod;
		return ret;
	}
};
vector<int>multiply(vector<int>A, vector<int>B, const int mod)
{
	for (int& a : A)
	{
		a %= mod;
		if (a < 0)a += mod;
	}
	for (int& b : B)
	{
		b %= mod;
		if (b < 0)b += mod;
	}
	vector<int>C1 = NTT<998244353, 3>().multiply(A, B);
	vector<int>C2 = NTT<469762049, 3>().multiply(A, B);
	vector<int>C3 = NTT<167772161, 3>().multiply(A, B);
	vector<int>C(C1.size());
	for (int i = 0; i < C.size(); i++)
	{
		long long v1 = C1[i];
		long long v2 = (C2[i] - v1) * 208783132 % 469762049;
		if (v2 < 0)v2 += 469762049;
		long long v3 = (C3[i] - v1 - v2 * 998244353) % 167772161 * 29562547 % 167772161;
		if (v3 < 0)v3 += 167772161;
		C[i] = (v1 + (v2 + v3 * 469762049) % mod * 998244353) % mod;
	}
	return C;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll mod = 1000000007;
	int n;
	cin >> n;
	vector<int> a(n + 1), b(n + 1);
	rep(i, n + 1) {
		cin >> a[i];
	}
	rep(i, n + 1) {
		cin >> b[i];
	}

	vector<int> c = multiply(a, b, mod);

	ll ans = 0;

	rep(i, n + 1) {
		(ans += c[i]) %= mod;
	}

	dunk(ans);

	return 0;
}
0