結果
| 問題 | No.3619 Compositional Power with Schröder Coordinate |
| コンテスト | |
| ユーザー |
 askr58
|
| 提出日時 | 2026-08-11 02:30:51 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 4,118 ms / 10,000 ms |
| + 643µs | |
| コード長 | 11,922 bytes |
| 記録 | |
| コンパイル時間 | 2,628 ms |
| コンパイル使用メモリ | 228,748 KB |
| 実行使用メモリ | 212,668 KB |
| 最終ジャッジ日時 | 2026-08-11 02:31:18 |
| 合計ジャッジ時間 | 25,286 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 6 |
ソースコード
#include <iostream>
#include <ranges>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;
//geneerated by Codex outside of contest time.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <vector>
#include <atcoder/convolution>
#include <atcoder/modint>
template <class Field = atcoder::modint998244353>
class FPS {
public:
using value_type = Field;
using size_type = std::size_t;
// 長さ n の零形式的冪級数を作る。
explicit FPS(size_type n = 0) : coefficients_(n) {}
// Field に変換できる型 U の係数列から作る。
template <class U>
explicit FPS(const std::vector<U>& coefficients) {
coefficients_.reserve(coefficients.size());
for (const auto& coefficient : coefficients) {
coefficients_.emplace_back(coefficient);
}
}
size_type size() const noexcept {
return coefficients_.size();
}
void resize(size_type n) {
coefficients_.resize(n);
}
Field& operator[](size_type i) {
return coefficients_[i];
}
const Field& operator[](size_type i) const {
return coefficients_[i];
}
FPS& operator+=(const FPS& rhs) {
const size_type old_size = size();
resize(std::max(size(), rhs.size()));
for (size_type i = 0; i < rhs.size(); ++i) {
if (i < old_size) {
coefficients_[i] += rhs[i];
} else {
coefficients_[i] = rhs[i];
}
}
return *this;
}
FPS& operator-=(const FPS& rhs) {
const size_type old_size = size();
resize(std::max(size(), rhs.size()));
for (size_type i = 0; i < rhs.size(); ++i) {
if (i < old_size) {
coefficients_[i] -= rhs[i];
} else {
coefficients_[i] = -rhs[i];
}
}
return *this;
}
FPS& operator*=(const FPS& rhs) {
return *this = *this * rhs;
}
// 形式的微分を求める。
FPS derivative() const {
if (size() == 0) {
return FPS();
}
FPS result(size() - 1);
for (size_type i = 1; i < size(); ++i) {
result[i - 1] = coefficients_[i] * Field(i);
}
return result;
}
// 競技プログラミングで一般的な名前も用意する。
FPS diff() const {
return derivative();
}
// 定数項を 0 として形式的積分を求める。
FPS integral() const {
FPS result(size() + 1);
for (size_type i = 0; i < size(); ++i) {
result[i + 1] = coefficients_[i] / Field(i + 1);
}
return result;
}
// this * result == 1 (mod x^size()) となる乗法逆元を求める。
FPS inv() const {
assert(size() > 0 && coefficients_[0] != Field(0));
FPS result(std::vector<Field>{coefficients_[0].inv()});
while (result.size() < size()) {
const size_type next_size = std::min(size(), result.size() * 2);
FPS prefix(next_size);
for (size_type i = 0; i < next_size; ++i) {
prefix[i] = coefficients_[i];
}
FPS correction = prefix * result;
correction.resize(next_size);
for (auto& coefficient : correction.coefficients_) {
coefficient = -coefficient;
}
correction[0] += Field(2);
result *= correction;
result.resize(next_size);
}
return result;
}
// log(this) (mod x^size()) を O(N log N) で求める。
FPS log() const {
assert(size() > 0 && coefficients_[0] == Field(1));
FPS result = derivative() * inv();
result.resize(size() - 1);
result = result.integral();
result.resize(size());
return result;
}
// exp(this) (mod x^size()) を Newton 法により O(N log N) で求める。
FPS exp() const {
if (size() == 0) {
return FPS();
}
assert(coefficients_[0] == Field(0));
FPS result(std::vector<Field>{Field(1)});
while (result.size() < size()) {
const size_type next_size = std::min(size(), result.size() * 2);
FPS prefix(next_size);
for (size_type i = 0; i < next_size; ++i) {
prefix[i] = coefficients_[i];
}
result.resize(next_size);
FPS correction = prefix - result.log();
correction[0] += Field(1);
result *= correction;
result.resize(next_size);
}
return result;
}
FPS& operator/=(const FPS& rhs) {
return *this = *this / rhs;
}
friend FPS operator+(FPS lhs, const FPS& rhs) {
lhs += rhs;
return lhs;
}
friend FPS operator-(FPS lhs, const FPS& rhs) {
lhs -= rhs;
return lhs;
}
// atcoder::convolution への依存は積の定義だけに閉じ込める。
friend FPS operator*(const FPS& lhs, const FPS& rhs) {
return FPS(atcoder::convolution(lhs.coefficients_, rhs.coefficients_));
}
friend FPS operator/(const FPS& lhs, FPS rhs) {
if (lhs.size() == 0) {
return FPS();
}
rhs.resize(std::max(rhs.size(), lhs.size()));
FPS quotient = lhs * rhs.inv();
quotient.resize(std::max(lhs.size(), rhs.size()));
return quotient;
}
private:
std::vector<Field> coefficients_;
};
// generated by Codex outside of contest time.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>
namespace composition_internal {
// Kinoshita--Li の Graeffe 再帰により f(g(x)) mod x^result_size を求める。
// g(0) = 0 を仮定する。
template <class Field>
FPS<Field> composition(FPS<Field> f, FPS<Field> g,
std::size_t result_size) {
if (result_size == 0) {
return FPS<Field>();
}
assert(g.size() == 0 || g[0] == Field(0));
// g の位数が正なので、result_size 次以上の f の係数は寄与しない。
if (f.size() > result_size) {
f.resize(result_size);
}
if (g.size() > result_size) {
g.resize(result_size);
}
std::size_t n = 1;
while (n < result_size || n < f.size()) {
assert(n <= std::numeric_limits<std::size_t>::max() / 2);
n *= 2;
}
f.resize(n);
g.resize(n);
// Q(x,y) は y の係数ごとに、長さ x_size のブロックへ格納する。
// 戻り値は y^(-m+1), ..., y^0 の係数を同じ形式で並べる。
const auto recurse = [&](auto&& self, const FPS<Field>& q,
std::size_t q_y_size,
std::size_t x_size,
std::size_t m) -> FPS<Field> {
if (x_size == 1) {
FPS<Field> result(m);
for (std::size_t block = 0; block < m; ++block) {
result[block] = f[m - 1 - block];
}
return result;
}
// y のブロック間隔を 2*x_size にして、x 次数の桁上がりを防ぐ。
const std::size_t stride = 2 * x_size;
FPS<Field> packed_q((q_y_size - 1) * stride + x_size);
FPS<Field> packed_q_minus((q_y_size - 1) * stride + x_size);
for (std::size_t y = 0; y < q_y_size; ++y) {
for (std::size_t x = 0; x < x_size; ++x) {
const Field value = q[y * x_size + x];
packed_q[y * stride + x] = value;
packed_q_minus[y * stride + x] =
(x % 2 == 0 ? value : -value);
}
}
// V(x^2,y) = Q(x,y)Q(-x,y)。
FPS<Field> packed_v = packed_q * packed_q_minus;
const std::size_t next_x_size = x_size / 2;
const std::size_t next_q_y_size =
std::min(n, 2 * q_y_size - 1);
FPS<Field> next_q(next_q_y_size * next_x_size);
for (std::size_t y = 0; y < next_q_y_size; ++y) {
for (std::size_t x = 0; x < next_x_size; ++x) {
const std::size_t index = y * stride + 2 * x;
if (index < packed_v.size()) {
next_q[y * next_x_size + x] = packed_v[index];
}
}
}
const std::size_t degree_y_q = q_y_size - 1;
const std::size_t next_m = std::min(n, m + degree_y_q);
FPS<Field> t = self(self, next_q, next_q_y_size,
next_x_size, next_m);
// U(x,y) = T(x^2,y)Q(-x,y)。T の最初のブロックは
// y^(-next_m+1) に対応する。
FPS<Field> packed_t((next_m - 1) * stride + x_size);
for (std::size_t y = 0; y < next_m; ++y) {
for (std::size_t x = 0; x < next_x_size; ++x) {
packed_t[y * stride + 2 * x] =
t[y * next_x_size + x];
}
}
FPS<Field> packed_u = packed_t * packed_q_minus;
FPS<Field> result(m * x_size);
const std::size_t first_source_block = next_m - m;
for (std::size_t y = 0; y < m; ++y) {
for (std::size_t x = 0; x < x_size; ++x) {
const std::size_t index =
(first_source_block + y) * stride + x;
if (index < packed_u.size()) {
result[y * x_size + x] = packed_u[index];
}
}
}
return result;
};
// Q(x,y) = 1 - y g(x)。
FPS<Field> q(2 * n);
q[0] = Field(1);
for (std::size_t i = 0; i < n; ++i) {
q[n + i] = -g[i];
}
FPS<Field> result = recurse(recurse, q, 2, n, 1);
result.resize(result_size);
return result;
}
} // namespace composition_internal
// f(g(x)) mod x^N を返す。N は二つの FPS の長さの最大値とする。
// 切り詰め FPS の合成なので g(0) = 0 を仮定する。
// Kinoshita--Li 法による計算量は O(M(N) log N) = O(N log^2 N)。
template <class Field>
FPS<Field> composition(const FPS<Field>& f, const FPS<Field>& g) {
return composition_internal::composition(
f, g, std::max(f.size(), g.size()));
}
// f(g(x)) = g(f(x)) = x mod x^N を満たす合成逆元 g を返す。
// N = f.size(), f(0) = 0, f'(0) != 0 を仮定する。
// 各 Newton 段の合成に Kinoshita--Li 法を用いる。
template <class Field>
FPS<Field> compositional_inv(const FPS<Field>& f) {
const std::size_t n = f.size();
if (n == 0) {
return FPS<Field>();
}
assert(f[0] == Field(0));
if (n == 1) {
return FPS<Field>(1);
}
assert(f[1] != Field(0));
FPS<Field> result(2);
result[1] = f[1].inv();
const FPS<Field> derivative = f.derivative();
std::size_t size = 2;
while (size < n) {
const std::size_t next_size = std::min(n, size * 2);
result.resize(next_size);
FPS<Field> error = composition_internal::composition(
f, result, next_size);
if (error.size() < 2) {
error.resize(2);
}
error[1] -= Field(1);
FPS<Field> composed_derivative =
composition_internal::composition(derivative, result, next_size);
composed_derivative.resize(next_size);
FPS<Field> correction = error * composed_derivative.inv();
correction.resize(next_size);
result -= correction;
result.resize(next_size);
size = next_size;
}
return result;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
FPS f(n),g(n),h(n);
for(int i=0;i<n;i++){
int t;
cin>>t;
f[i]=t;
}
for(int i=0;i<n;i++){
int t;
cin>>t;
g[i]=t;
g[i]*=f[1].pow(m);
}
for(int i=0;i<n;i++){
int t;
cin>>t;
h[i]=t;
}
auto ans=composition(h,g);
for(int i=0;i<n;i++)cout<<ans[i].val()<<(i+1==n?"\n":" ");
}