結果

問題 No.3620 Compositional Power with Schröder Coordinate 2
コンテスト
ユーザー shobonvip
提出日時 2026-08-10 22:00:31
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 3,350 ms / 10,000 ms
+ 552µs
コード長 8,821 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,019 ms
コンパイル使用メモリ 397,496 KB
実行使用メモリ 97,128 KB
最終ジャッジ日時 2026-08-11 00:00:18
合計ジャッジ時間 23,301 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/**
	author:  shobonvip
	created: 2026.08.10 21:34:23
**/

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

//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/

/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/

typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}

// https://noshi91.hatenablog.com/entry/2024/03/16/224034
// https://atcoder.jp/contests/abc345/submissions/51359643

// https://qoj.ac/submission/356957
// hos_lyricさんの提出を改変
/*
  q: rev([0, m]) * [0, n], [t^0] q(t, x) = 1 omitted
  ret: [0, m-1] * [0, n]
*/

vector<mint> comRec(int m, int n, const vector<mint> &as, const vector<mint> &qss) {
  if (!n) { auto ret = as; ret.resize(m, 0); return ret; }
  // reuse DFT(q(t, -x)); (2n+2) instead of (2n+1)
  int len;
  for (len = 2; len < (2*m) * (2*n+2); len <<= 1) {}
  vector<mint> qs(len, 0);
  for (int i = 0; i < m; ++i) for (int j = 0; j <= n; ++j) qs[i * (2*n+2) + j] = qss[i * (n+1) + j];
  internal::butterfly(qs);
  vector<mint> work(len >> 1, 0);
  for (int k = 0; k < len >> 1; ++k) { work[k] = qs[k << 1] * qs[k << 1 | 1]; swap(qs[k << 1], qs[k << 1 | 1]); }
  internal::butterfly_inv(work);
  {
	mint tmp = mint((int)work.size()).inv();
	for (int k = 0; k < len >> 1; ++k) work[k] *= tmp;
  }
  vector<mint> qqss((2*m) * (n/2+1), 0);
  for (int i = 0; i < 2*m-1; ++i) for (int j = 0; j <= n/2; ++j) qqss[i * (n/2+1) + j] = work[i * (n+1) + j];
  for (int i = 0; i < m; ++i) for (int j = 0; j <= n/2; ++j) qqss[(m+i) * (n/2+1) + j] += qss[i * (n+1) + 2*j] + qss[i * (n+1) + 2*j];
  const auto res = comRec(2*m, n/2, as, qqss);
  vector<mint> ps(len, 0);
  for (int i = 0; i < 2*m; ++i) for (int j = 0; j <= n/2; ++j) ps[i * (2*n+2) + (2*n+1) - (2*j+(n&1))] = res[i * (n/2+1) + j];
  internal::butterfly(ps);
  for (int k = 0; k < len; ++k) ps[k] *= qs[k];
  internal::butterfly_inv(ps);
  {
	mint tmp = mint((int)ps.size()).inv();
    for (int k = 0; k < len; ++k) ps[k] *= tmp;
  }
  vector<mint> ret(m * (n+1));
  for (int i = 0; i < m; ++i) for (int j = 0; j <= n; ++j) ret[i * (n+1) + j] = ps[(m+i) * (2*n+2) + (2*n+1) - j];
  for (int i = 0; i < m; ++i) for (int j = 0; j <= n/2; ++j) ret[i * (n+1) + (2*j+(n&1))] += res[i * (n/2+1) + j];
  return ret;
}

/*
  a(b(x))
  transpose and rev: p(x) -> [x^(N-1)] p(x) b(x)^i for each i
  [x^(N-1)] p(x) / (1 - t b(x))
*/
vector<mint> com(int n, const vector<mint> &as, const vector<mint> &bs) {
  assert((int)as.size() <= n);
  assert((int)bs.size() <= n);
  vector<mint> qss(n, 0);
  for (int j = 0; j < (int)bs.size(); ++j) qss[j] = -bs[j];
  auto cs = comRec(1, n - 1, as, qss);
  reverse(cs.begin(), cs.end());
  return cs;
}
// ここまで hos_lyricさんの提出を一部改変

// maspyさんの実装をほぼ写した
// https://noshi91.hatenablog.com/entry/2024/03/16/224034
// https://atcoder.jp/contests/abc345/submissions/51359643


template <typename mint>
vector<mint> poly_inv(vector<mint> &a, int M = -314159265){
	if (M == -314159265) M = (int)a.size();
	else if (M <= 0) return {};
	int n = a.size();
	mint r = a[0].pow((ll)(mint::mod())-2);
	int m = 1;
	vector<mint> res = {r};
	while (m < M){
		vector<mint> f = a;
		f.resize(2 * m);
		vector<mint> g = res;
		g.resize(2 * m);
		internal::butterfly(f);
		internal::butterfly(g);
		for (int i=0; i<2*m; i++){
			f[i] = f[i] * g[i];
		}
		internal::butterfly_inv(f);
		for (int i=0; i<m; i++){
			f[i] = f[i + m];
		}
		for (int i=0; i<m; i++){
			f[i + m] = 0;
		}
		internal::butterfly(f);
		for (int i=0; i<2*m; i++){
			f[i] = f[i] * g[i];
		}
		internal::butterfly_inv(f);
		mint iz = mint(2*m).inv();
		iz = -iz * iz;
		for (int i=0; i<m; i++){
			f[i] = f[i] * iz;
		}
		res.insert(res.end(), f.begin(), f.begin()+m);
		m <<= 1;
	}
	res.resize(M);
	return res;
}

template <typename mint>
vector<vector<mint>> convolution2d(vector<vector<mint>> &f, vector<vector<mint>> &g){
	auto shape = [&](vector<vector<mint>> &f) -> pair<int,int> {
		int h = (int)f.size();
		int w = (h == 0 ? 0: (int)f[0].size());
		return pair(h, w);
	};

	auto [h1, w1] = shape(f);
	auto [h2, w2] = shape(g);
	int h = h1 + h2 - 1;
	int w = w1 + w2 - 1;

	vector<mint> ff(h1 * w);
	vector<mint> gg(h2 * w);
	for (int x=0; x<h1; x++){
		for (int y=0; y<w1; y++){
			ff[x * w + y] = f[x][y];
		}
	}
	for (int x=0; x<h2; x++){
		for (int y=0; y<w2; y++){
			gg[x * w + y] = g[x][y];
		}
	}
	vector<mint> rr = convolution(ff, gg);
	vector<vector<mint>> ret(h, vector<mint>(w));
	for (int x=0; x<h; x++){
		for (int y=0; y<w; y++){
			ret[x][y] = rr[x * w + y];
		}
	}
	return ret;
}

template <typename mint>
vector<mint> poly_div(vector<mint> f, vector<mint> g){
	int n = (int)f.size();
	g.resize(n);
	g = poly_inv(g);
	f = convolution(f, g);
	f.resize(n);
	return f;
}

// ここまで maspy さんのほぼ写し

// Fix k, find [x^k] f(x) g(x)^i for i = 0,1,...,n-1
// O((n+k) log^2 (n+k))
template <typename mint>
vector<mint> shobon_coef_of_fps_pows(vector<mint> g, int k, int n, vector<mint> f = {mint(1)}){
	// Assume [x^0] g(x) = 0
	// あとで g(x) \ne 0 の場合を処理するコードをかく
	f.resize(k+1);
	g.resize(k+1);
	vector P(k+1, vector<mint>(2));
	vector Q(k+1, vector<mint>(2));
	for (int i=0; i<k+1; i++) P[i][0] = f[i];
	Q[0][0] = 1;
	for (int i=0; i<k+1; i++) Q[i][1] = - g[i];

	while (k > 0){
		vector<vector<mint>> QI = Q;
		for (int i=0; i<(int)Q.size(); i++){
			if (i%2 == 0) continue;
			for (int j=0; j<(int)Q[0].size(); j++){
				QI[i][j] = -Q[i][j];
			}
		}
		vector<vector<mint>> QQ = convolution2d(Q, QI);
		vector<vector<mint>> PP = convolution2d(P, QI);
		Q.resize(((int)Q.size()+1)/2);
		for (int i=0; i<(int)Q.size(); i++){
			Q[i] = QQ[2*i];
		}
		if (k%2==0){
			P.resize(((int)P.size()+1)/2);
			for (int i=0; i<(int)P.size(); i++){
				P[i] = PP[2*i];
			}
		}else{
			P.resize((int)P.size()/2);
			for (int i=0; i<(int)P.size(); i++){
				P[i] = PP[2*i+1];
			}
		}
		for (int i=0; i<(int)P.size(); i++){
			if ((int)P[i].size() > n){
				P[i].resize(n);
			}else{
				break;
			}
		}
		for (int i=0; i<(int)Q.size(); i++){
			if ((int)Q[i].size() > n){
				Q[i].resize(n);
			}else{
				break;
			}
		}
		k >>= 1;
	}

	P[0].resize(n);
	Q[0].resize(n);
	return poly_div(P[0], Q[0]);
}

int ceil_pow2(int n) {
	int x = 0;
	while ((1U << x) < (unsigned int)(n)) x++;
	return x;
}

vector<mint> multi_eval(vector<mint> x, vector<mint> a){
	int n = x.size();
	int siz = 1 << ceil_pow2(n);
	vector<vector<mint>> g(2*siz, vector<mint>{1});
	for (int i=0; i<n; i++) g[i + siz] = {-x[i], 1};
	for (int i=siz-1; i>0; i--) g[i] = convolution(g[2*i], g[2*i+1]);
	vector<mint> f;
	for (int i=1; i<2*siz; i++){
		if (i==1) f = a;
		else f = g[i>>1];
		int fs = f.size(), gs = g[i].size();
		int m = fs - gs + 1;
		vector<mint> v = {}, w = {};
		if (m > 0){
			vector<mint> ft(m);
			for (int j=0; j<m; j++) ft[j] = f[fs-1-j];
			vector<mint> gt(gs);
			for (int j=0; j<gs; j++) gt[j] = g[i][gs-1-j];
			v = convolution(ft, poly_inv(gt, m));
			v.resize(m);
			reverse(v.begin(), v.end());
			w = convolution(v, g[i]);
		}
		g[i] = f;
		for (int j=0; j<w.size(); j++){
			g[i][j] -= w[j];
		}
		while (g[i].size() > 1 && g[i][g[i].size() - 1] == 0){
			g[i].pop_back();
		}
	}
	vector<mint> ret(n);
	for (int i=0; i<n; i++){
		ret[i] = g[i+siz][0];
	}
	return ret;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,m;
	cin >> n >> m;
	vector<mint> a(n), b(n), c(n);
	rep(i,0,n) {int x; cin >> x; a[i] = x;}
	rep(i,0,n) {int x; cin >> x; b[i] = x;}
	rep(i,0,n) {int x; cin >> x; c[i] = x;}

	// (h[i] [x^(n-1)] g(x)^i) for i = 0, 1, ..., n-1
	vector<mint> d = shobon_coef_of_fps_pows(b, n-1, n);
	rep(i,0,n) {
		d[i] *= c[i];
	}

	// for each k
	// sum[i=0,m-1] d[i] * a[1]^(ik) is the answer.
	// so d(a[1]^k) is an answer.
	// this is multipoint evaluation!

	vector<mint> points(m);
	mint v = 1;
	rep(i,0,m) {
		points[i] = v;
		v *= a[1];
	}

	vector<mint> f = multi_eval(points, d);
	for (auto &x: f) cout << x.val() << ' ';
	cout << '\n';

}
0