#1176073 (C++23) No.3619 Compositional Power with Schröder Coordinate

• 問題: No.3619 Compositional Power with Schröder Coordinate
• ユーザー: shobonvip
• 提出日時: 2026-08-10 21:37:23
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,099 ms / 10,000 ms
• コード長: 3,947 bytes
• コンパイル時間: 4,328 ms
• コンパイル使用メモリ: 383,876 KB
• 実行使用メモリ: 139,312 KB
• 最終ジャッジ日時: 2026-08-10 21:37:35
• 合計ジャッジ時間: 11,970 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 6

ソースコード

/**
	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さんの提出を一部改変

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;}

	mint v = a[1].pow(m);
	vector<mint> f = b;
	for (auto &x: f) x *= v;

	f = com(n, c, f);
	for (auto &x: f) cout << x.val() << ' ';
	cout << '\n';

	
}