結果

問題 No.931 Multiplicative Convolution
ユーザー kazumakazuma
提出日時 2019-11-23 12:52:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 167 ms / 2,000 ms
コード長 3,117 bytes
コンパイル時間 2,357 ms
コンパイル使用メモリ 202,288 KB
実行使用メモリ 8,196 KB
最終ジャッジ日時 2024-04-19 14:37:54
合計ジャッジ時間 4,397 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 17 ms
5,376 KB
testcase_08 AC 166 ms
8,196 KB
testcase_09 AC 112 ms
7,832 KB
testcase_10 AC 154 ms
7,896 KB
testcase_11 AC 116 ms
7,812 KB
testcase_12 AC 128 ms
7,140 KB
testcase_13 AC 161 ms
7,956 KB
testcase_14 AC 167 ms
8,064 KB
testcase_15 AC 166 ms
8,196 KB
testcase_16 AC 160 ms
7,956 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int mod_inv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b > 0) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	return (u % m + m) % m;
}

ll mod_pow(ll x, ll y, ll md) {
	ll res = 1;
	while (y) {
		if (y & 1) res = res * x % md;
		x = x * x % md;
		y >>= 1;
	}
	return res;
}

template <int Mod, int PrimitiveRoot>
class fast_modulo_transform {
public:
	static vector<int> fft(vector<int> v, bool inv) {
		const int N = v.size();
		assert((N ^ (N & -N)) == 0);
		int ww = mod_pow(PrimitiveRoot, (Mod - 1) / N, Mod);
		if (inv) ww = mod_inv(ww, Mod);
		for (int m = N; m >= 2; m >>= 1) {
			const int mh = m >> 1;
			int w = 1;
			for (int i = 0; i < mh; ++i) {
				for (int j = i; j < N; j += m) {
					const int k = j + mh;
					int x = v[j] - v[k];
					if (x < 0) x += Mod;
					v[j] += -Mod + v[k];
					if (v[j] < 0) v[j] += Mod;
					v[k] = (1LL * w * x) % Mod;
				}
				w = (1LL * w * ww) % Mod;
			}
			ww = (1LL * ww * ww) % Mod;
		}
		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(v[i], v[j]);
		}
		if (inv) {
			const int inv_n = mod_inv(N, Mod);
			for (auto& x : v) {
				x = (1LL * x * inv_n) % Mod;
				assert(0 <= x && x < Mod);
			}
		}
		return v;
	}
	static vector<int> convolution(vector<int> f, vector<int> g) {
		int sz = 1;
		const int m = f.size() + g.size() - 1;
		while (sz < m) sz *= 2;
		f.resize(sz), g.resize(sz);
		f = fast_modulo_transform::fft(move(f), false); g = fast_modulo_transform::fft(move(g), false);
		for (int i = 0; i < sz; ++i) {
			f[i] = (1LL * f[i] * g[i]) % Mod;
		}
		return fast_modulo_transform::fft(move(f), true);
	}
};

const int mod = 998244353;

using fmt = fast_modulo_transform<998244353, 3>;

int mod_pow(int a, int b, int m) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = 1LL * ret * a % m;
		a = 1LL * a * a % m;
		b >>= 1;
	}
	return ret;
}

template <typename T>
T get_primitive_root(T p) { // p is prime
	vector<T> fac;
	T v = p - 1;
	for (T pp = 2; pp * pp <= v; pp++) if (v % pp == 0) {
		while (v % pp == 0) v /= pp;
		fac.push_back(pp);
	}
	if (v > 1) fac.push_back(v);
	for (T g = 2; g < p; g++) {
		assert(mod_pow(g, p - 1, p) == 1);
		bool ok = true;
		for (auto pp : fac) {
			if (mod_pow(g, (p - 1) / pp, p) == 1) {
				ok = false;
				break;
			}
		}
		if (ok) return g;
	}
	return -1;
}

int main()
{
	int P;
	cin >> P;
	vector<int> A(P), B(P);
	for (int i = 1; i < P; i++) {
		cin >> A[i];
	}
	for (int i = 1; i < P; i++) {
		cin >> B[i];
	}
	int rt = get_primitive_root(P);
	vector<int> v(P), pos(P);
	for (int i = 0; i < P - 1; i++) {
		int x = mod_pow(rt, i, P);
		v[i] = x;
		pos[x] = i;
	}
	vector<int> a(P), b(P);
	for (int i = 0; i < P - 1; i++) {
		a[i] = A[v[i]];
		b[i] = B[v[i]];
	}
	auto c = fmt::convolution(a, b);
	for (int i = P - 1; i < (int)c.size(); i++) {
		(c[i % (P - 1)] += c[i]) %= mod;
	}
	vector<int> C(P);
	for (int i = 0; i < P - 1; i++) {
		C[v[i]] = c[i];
	}
	for (int i = 1; i < P; i++) {
		cout << C[i] << " \n"[i + 1 == P];
	}
	return 0;
}
0