#1196535 (C++17) No.3793 Multishift

• 問題: No.3793 Multishift
• ユーザー: 👑 AngrySadEight
• 提出日時: 2026-11-02 09:19:27
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2,354 ms / 7,000 ms
• コード長: 11,356 bytes
• コンパイル時間: 3,744 ms
• コンパイル使用メモリ: 246,896 KB
• 実行使用メモリ: 94,772 KB
• 最終ジャッジ日時: 2026-11-06 21:12:28
• 合計ジャッジ時間: 23,079 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge7_0

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

ソースコード

#include <algorithm>
#include <atcoder/all>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using namespace atcoder;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repk(i, k, n) for (int i = k; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define mod1 1000000007
#define mod2 998244353
#define mod3 100000007
#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vvc vector<vector<char>>
#define vvl vector<vector<ll>>
#define vvb vector<vector<bool>>
#define vvvi vector<vector<vector<int>>>
#define vvvl vector<vector<vector<ll>>>
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define vvpii vector<vector<pair<int, int>>>
#define vvpll vector<vector<pair<ll, ll>>>

template <typename T>
void debug(T e) {
    cerr << e << endl;
}

template <typename T>
void debug(vector<T> &v) {
    rep(i, v.size()) { cerr << v[i] << " "; }
    cerr << endl;
}

template <typename T>
void debug(vector<vector<T>> &v) {
    rep(i, v.size()) {
        rep(j, v[i].size()) { cerr << v[i][j] << " "; }
        cerr << endl;
    }
}

template <typename T>
void debug(vector<pair<T, T>> &v) {
    rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; }
}

template <typename T>
void debug(set<T> &st) {
    for (auto itr = st.begin(); itr != st.end(); itr++) {
        cerr << *itr << " ";
    }
    cerr << endl;
}

template <typename T>
void debug(multiset<T> &ms) {
    for (auto itr = ms.begin(); itr != ms.end(); itr++) {
        cerr << *itr << " ";
    }
    cerr << endl;
}

template <typename T>
void debug(map<T, T> &mp) {
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        cerr << itr->first << " " << itr->second << endl;
    }
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << H << " ";
    debug_out(T...);
}

using mint = modint998244353;

void debug_mint1(vector<mint> &vec) {
    for (int i = 0; i < vec.size(); i++) {
        cerr << vec[i].val() << " ";
    }
    cerr << endl;
}

void debug_mint2(vector<vector<mint>> &vec) {
    for (int i = 0; i < vec.size(); i++) {
        for (int j = 0; j < vec[i].size(); j++) {
            cerr << vec[i][j].val() << " ";
        }
        cerr << endl;
    }
}

// 多点評価 （ChatGPT に書かせたやつ）
// using mint = atcoder::modint998244353;
using Poly = vector<mint>;

// 末尾の 0 を除去する
void normalize(Poly& f) {
    while (f.size() > 1 && f.back() == mint(0)) {
        f.pop_back();
    }
    if (f.empty()) f.push_back(0);
}

// 多項式の積
Poly multiply(const Poly& a, const Poly& b) {
    return atcoder::convolution(a, b);
}

// 形式的冪級数の逆元
// f[0] != 0 を仮定
// f * g = 1 (mod x^n) となる g を返す
Poly fps_inv(const Poly& f, int n) {
    if (n == 0) return {};

    assert(!f.empty() && f[0] != mint(0));

    Poly g = {f[0].inv()};

    for (int k = 1; k < n; k *= 2) {
        int m = min(2 * k, n);

        Poly a(min((int)f.size(), m));
        for (int i = 0; i < (int)a.size(); i++) {
            a[i] = f[i];
        }

        // g <- g * (2 - f*g) mod x^m
        Poly t = multiply(a, g);
        t.resize(m);
        for (auto& x : t) x = -x;
        t[0] += 2;

        g = multiply(g, t);
        g.resize(m);
    }

    return g;
}

// 多項式の剰余 a mod b
// b != 0 を仮定
Poly poly_mod(Poly a, Poly b) {
    normalize(a);
    normalize(b);

    assert(!(b.size() == 1 && b[0] == mint(0)));

    int n = (int)a.size();
    int m = (int)b.size();

    if (n < m) return a;
    if (m == 1) return {0};

    int k = n - m + 1;

    // 商 q = a / b を反転多項式から求める
    Poly ra(a.rbegin(), a.rend());
    Poly rb(b.rbegin(), b.rend());

    ra.resize(k);

    Poly ib = fps_inv(rb, k);
    Poly rq = multiply(ra, ib);
    rq.resize(k);

    Poly q(rq.rbegin(), rq.rend());

    // 余り r = a - b*q
    Poly bq = multiply(b, q);

    Poly r(m - 1, mint(0));
    for (int i = 0; i < m - 1; i++) {
        r[i] = a[i] - bq[i];
    }

    normalize(r);
    return r;
}

// 多点評価
// f[i] は x^i の係数
// 戻り値 res[i] = f(xs[i])
vector<mint> multipoint_evaluation(
    const vector<mint>& f,
    const vector<mint>& xs
) {
    int m = (int)xs.size();
    if (m == 0) return {};

    int sz = 1;
    while (sz < m) sz *= 2;

    // 積木
    // tree[v] = 対応する (x - xs[i]) の積
    vector<Poly> tree(2 * sz);

    for (int i = 0; i < sz; i++) {
        if (i < m) {
            tree[sz + i] = {-xs[i], mint(1)};
        } else {
            tree[sz + i] = {mint(1)};
        }
    }

    for (int i = sz - 1; i >= 1; i--) {
        tree[i] = multiply(
            tree[2 * i],
            tree[2 * i + 1]
        );
    }

    // 各ノードにおける f の剰余
    vector<Poly> rem(2 * sz);

    if (f.empty()) {
        rem[1] = {0};
    } else {
        rem[1] = poly_mod(f, tree[1]);
    }

    for (int i = 1; i < sz; i++) {
        rem[2 * i] = poly_mod(
            rem[i], tree[2 * i]
        );
        rem[2 * i + 1] = poly_mod(
            rem[i], tree[2 * i + 1]
        );
    }

    vector<mint> res(m);
    for (int i = 0; i < m; i++) {
        res[i] = rem[sz + i][0];
    }

    return res;
}

// 多項式補間 (ChatGPT に書かせたやつ)
// 末尾の 0 を除去
void normalize2(Poly& a) {
    while (!a.empty() && a.back() == 0) a.pop_back();
}

// 多項式の加算
Poly poly_add(const Poly& a, const Poly& b) {
    Poly c(max(a.size(), b.size()));
    for (int i = 0; i < (int)a.size(); i++) c[i] += a[i];
    for (int i = 0; i < (int)b.size(); i++) c[i] += b[i];
    normalize(c);
    return c;
}

// 多項式の乗算
Poly poly_mul(const Poly& a, const Poly& b) {
    if (a.empty() || b.empty()) return {};
    return convolution(a, b);
}

// f(x)^(-1) mod x^n
// f[0] != 0 を仮定
Poly poly_inv(const Poly& f, int n) {
    if (n == 0) return {};

    Poly g = {f[0].inv()};

    while ((int)g.size() < n) {
        int m = min(n, (int)g.size() * 2);

        Poly t(min((int)f.size(), m));
        for (int i = 0; i < (int)t.size(); i++) {
            t[i] = f[i];
        }

        t = poly_mul(t, g);
        t.resize(m);

        for (auto& x : t) x = -x;
        t[0] += 2;

        g = poly_mul(g, t);
        g.resize(m);
    }

    return g;
}

// a(x) mod b(x)
// b != 0 を仮定
Poly poly_mod2(Poly a, const Poly& b) {
    normalize(a);

    if (a.size() < b.size()) return a;
    if (b.size() == 1) return {};

    int k = (int)a.size() - (int)b.size() + 1;

    Poly ra = a, rb = b;
    reverse(ra.begin(), ra.end());
    reverse(rb.begin(), rb.end());

    ra.resize(k);
    Poly inv_rb = poly_inv(rb, k);

    Poly q = poly_mul(ra, inv_rb);
    q.resize(k);
    reverse(q.begin(), q.end());

    Poly t = poly_mul(q, b);

    for (int i = 0; i < (int)t.size(); i++) {
        a[i] -= t[i];
    }

    a.resize(b.size() - 1);
    normalize2(a);
    return a;
}

// 多項式の微分
Poly poly_derivative(const Poly& f) {
    if (f.size() <= 1) return {};

    Poly g(f.size() - 1);
    for (int i = 1; i < (int)f.size(); i++) {
        g[i - 1] = f[i] * i;
    }
    return g;
}

struct SubproductTree {
    int n, sz;
    vector<Poly> prod;

    SubproductTree(const vector<mint>& xs) {
        n = xs.size();
        sz = 1;
        while (sz < n) sz <<= 1;

        prod.resize(sz * 2);

        for (int i = 0; i < sz; i++) {
            if (i < n) {
                prod[sz + i] = {-xs[i], 1};
            } else {
                prod[sz + i] = {1};
            }
        }

        for (int i = sz - 1; i >= 1; i--) {
            prod[i] = poly_mul(prod[i * 2], prod[i * 2 + 1]);
        }
    }

    // f(x_i) をすべて計算
    vector<mint> evaluate(const Poly& f) const {
        vector<mint> res(n);
        if (n == 0) return res;

        auto dfs = [&](auto&& self, int v, const Poly& r) -> void {
            if (v >= sz) {
                int i = v - sz;
                if (i < n) {
                    res[i] = r.empty() ? mint(0) : r[0];
                }
                return;
            }

            Poly l = poly_mod2(r, prod[v * 2]);
            Poly rr = poly_mod2(r, prod[v * 2 + 1]);

            self(self, v * 2, l);
            self(self, v * 2 + 1, rr);
        };

        dfs(dfs, 1, poly_mod2(f, prod[1]));
        return res;
    }

    // w_i から補間多項式を構成
    // Σ w_i * prod[1](x) / (x - x_i)
    Poly build(const vector<mint>& w) const {
        if (n == 0) return {};

        auto dfs = [&](auto&& self, int v) -> Poly {
            if (v >= sz) {
                int i = v - sz;
                return i < n ? Poly{w[i]} : Poly{};
            }

            Poly l = self(self, v * 2);
            Poly r = self(self, v * 2 + 1);

            Poly a = poly_mul(l, prod[v * 2 + 1]);
            Poly b = poly_mul(r, prod[v * 2]);

            return poly_add(a, b);
        };

        return dfs(dfs, 1);
    }
};

// 多項式補間
// 入力: (x_i, y_i) の配列
// 出力: f(x) の係数 (定数項から昇順)
// x_i は互いに相異なると仮定
vector<mint> polynomial_interpolation(
    const vector<pair<mint, mint>>& points
) {
    int n = points.size();
    if (n == 0) return {};

    vector<mint> xs(n), ys(n);
    for (int i = 0; i < n; i++) {
        xs[i] = points[i].first;
        ys[i] = points[i].second;
    }

    SubproductTree tree(xs);

    // P(x) = Π (x - x_i)
    const Poly& P = tree.prod[1];

    // P'(x_i) を計算
    Poly dP = poly_derivative(P);
    vector<mint> den = tree.evaluate(dP);

    // w_i = y_i / P'(x_i)
    vector<mint> w(n);
    for (int i = 0; i < n; i++) {
        assert(den[i] != 0);
        w[i] = ys[i] / den[i];
    }

    // f(x) = Σ w_i * P(x) / (x - x_i)
    Poly f = tree.build(w);
    f.resize(n);
    return f;
}

int main() {
    ll N, M;
    cin >> N >> M;
    vector<mint> A(N + 1);
    rep(i, N + 1){
        ll a;
        cin >> a;
        A[i] = mint(a);
    }
    vector<mint> B(M + 1);
    rep(i, M + 1){
        ll b;
        cin >> b;
        B[i] = mint(b);
    }

    // 多点評価、多項式補間　→　OK
    // この 2 つの道具を揃えるハードルが高いが、そろっていれば難しくはない
    vector<mint> pts;
    for (ll i = -M; i <= N; i++){
        pts.push_back(mint(mod2 + i));
    }

    vector<mint> f = multipoint_evaluation(A, pts);
    vector<mint> g = convolution(f, B);
    vector<pair<mint, mint>> comb_g;
    for (ll i = M; i <= M + N; i++){
        comb_g.push_back(make_pair(mint(i - M), g[i]));
    }
    vector<mint> ans = polynomial_interpolation(comb_g);
    for (ll i = 0; i <= N; i++){
        cout << ans[i].val();
        if (i < N) cout << " ";
    }
    cout << endl;
}