#1195910 (C++23) No.3793 Multishift

• 問題: No.3793 Multishift
• ユーザー: hiro1729
• 提出日時: 2026-10-30 07:44:59
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,556 ms / 7,000 ms
• コード長: 4,524 bytes
• コンパイル時間: 4,495 ms
• コンパイル使用メモリ: 374,748 KB
• 実行使用メモリ: 66,948 KB
• 最終ジャッジ日時: 2026-11-06 21:10:42
• 合計ジャッジ時間: 20,310 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 13

ソースコード

#include <bits/stdc++.h>
#include <atcoder/convolution>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;
using poly = vector<mint>;

poly poly_inv(const poly& f, int n) {
	poly g = {f[0].inv()};
	while ((int)g.size() < n) {
		int k = g.size() * 2;
		poly fk(f.begin(), f.begin() + min<int>(k, f.size()));
		poly t = atcoder::convolution(g, g);
		t = atcoder::convolution(t, fk);
		t.resize(k);
		poly ng(k);
		for (int i = 0; i < k; i++) {
			mint a = i < (int)g.size() ? g[i] * 2 : mint(0);
			ng[i] = a - t[i];
		}
		g = move(ng);
	}
	g.resize(n);
	return g;
}

vector<mint> multipoint_evaluation(const poly& f, const vector<mint>& p) {
	int n = f.size(), m = p.size();
	if (m == 0) return {};
	if (n == 0) return vector<mint>(m, mint(0));
	int L = max(n, m);
	poly pts = p;
	pts.resize(L, mint(0));

	int sz = 1;
	while (sz < L) sz <<= 1;
	vector<poly> g(4 * L + 4);
	auto build = [&](auto&& self, int node, int l, int r) -> void {
		if (r - l == 1) {
			g[node] = {mint(1), -pts[l]};
			return;
		}
		int mid = (l + r) / 2;
		self(self, node * 2, l, mid);
		self(self, node * 2 + 1, mid, r);
		g[node] = atcoder::convolution(g[node * 2], g[node * 2 + 1]);
	};
	build(build, 1, 0, L);

	poly frev(f.rbegin(), f.rend());
	frev.resize(L, mint(0));
	{
		poly fe = f;
		fe.resize(L, mint(0));
		frev.assign(fe.rbegin(), fe.rend());
	}
	poly inv = poly_inv(g[1], L);
	poly A = atcoder::convolution(frev, inv);
	A.resize(L);

	vector<mint> ans(L);
	auto descend = [&](auto&& self, int node, int l, int r, poly a) -> void {
		if (r - l == 1) {
			ans[l] = a[0];
			return;
		}
		int mid = (l + r) / 2;
		int sl = mid - l, sr = r - mid, s = r - l;
		poly B = atcoder::convolution(a, g[node * 2 + 1]);
		poly C = atcoder::convolution(a, g[node * 2]);
		poly al(B.begin() + sr, B.begin() + sr + sl);
		poly ar(C.begin() + sl, C.begin() + sl + sr);
		(void)s;
		self(self, node * 2, l, mid, move(al));
		self(self, node * 2 + 1, mid, r, move(ar));
	};
	descend(descend, 1, 0, L, move(A));
	ans.resize(m);
	return ans;
}

poly lagrange_interpolation(const vector<mint>& x, const vector<mint>& y) {
	int n = x.size();
	if (n == 0) return {};

	vector<poly> P(4 * n + 4);
	auto build = [&](auto&& self, int node, int l, int r) -> void {
		if (r - l == 1) {
			P[node] = {-x[l], mint(1)};
			return;
		}
		int mid = (l + r) / 2;
		self(self, node * 2, l, mid);
		self(self, node * 2 + 1, mid, r);
		P[node] = atcoder::convolution(P[node * 2], P[node * 2 + 1]);
	};
	build(build, 1, 0, n);

	poly dP(n);
	for (int i = 0; i < n; i++) dP[i] = P[1][i + 1] * (i + 1);
	vector<mint> d = multipoint_evaluation(dP, x);

	auto combine = [&](auto&& self, int node, int l, int r) -> poly {
		if (r - l == 1) return poly{y[l] / d[l]};
		int mid = (l + r) / 2;
		poly a = self(self, node * 2, l, mid);
		poly b = self(self, node * 2 + 1, mid, r);
		poly c1 = atcoder::convolution(a, P[node * 2 + 1]);
		poly c2 = atcoder::convolution(b, P[node * 2]);
		poly res(max(c1.size(), c2.size()));
		for (size_t i = 0; i < c1.size(); i++) res[i] += c1[i];
		for (size_t i = 0; i < c2.size(); i++) res[i] += c2[i];
		return res;
	};
	poly res = combine(combine, 1, 0, n);
	res.resize(n);
	return res;
}

mint lagrange_interpolation_at(const vector<mint>& y, long long a) {
	int n = y.size();
	if (n == 0) return 0;
	mint am = a;
	if (a >= 0 && a < n) return y[a];
	vector<mint> fact(n), ifact(n), pre(n + 1), suf(n + 1);
	fact[0] = 1;
	for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i;
	ifact[n - 1] = fact[n - 1].inv();
	for (int i = n - 1; i > 0; i--) ifact[i - 1] = ifact[i] * i;
	pre[0] = 1;
	for (int i = 0; i < n; i++) pre[i + 1] = pre[i] * (am - i);
	suf[n] = 1;
	for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] * (am - i);
	mint ans = 0;
	for (int i = 0; i < n; i++) {
		mint t = y[i] * pre[i] * suf[i + 1] * ifact[i] * ifact[n - 1 - i];
		if ((n - 1 - i) & 1) ans -= t;
		else ans += t;
	}
	return ans;
}

int main() {
	int N, M; cin >> N >> M;
	vector<mint> A(N + 1), B(M + 1);
	for (int i = 0; i <= N; i++) {
		int a; cin >> a;
		A[i] = a;
	}
	for (int i = 0; i <= M; i++) {
		int b; cin >> b;
		B[i] = b;
	}
	vector<mint> P(N + M + 1); iota(P.begin(), P.end(), -M);
	vector<mint> Y = multipoint_evaluation(A, P);
	vector<mint> Q = atcoder::convolution(Y, B);
	vector<mint> R(N + 1);
	for (int i = 0; i <= N; i++) R[i] = Q[M + i];
	vector<mint> xs(N + 1); iota(xs.begin(), xs.end(), 0);
	vector<mint> g = lagrange_interpolation(xs, R);
	for (mint i: g) {
		cout << i.val() << ' ';
	}
	cout << '\n';
}