結果

問題 No.1985 [Cherry 4th Tune] Early Summer Rain
コンテスト
ユーザー cologne
提出日時 2022-04-27 20:01:16
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5,390 ms / 7,000 ms
コード長 7,885 bytes
コンパイル時間 3,943 ms
コンパイル使用メモリ 166,152 KB
実行使用メモリ 112,292 KB
最終ジャッジ日時 2024-11-15 02:21:48
合計ジャッジ時間 112,817 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")

#include <algorithm>
#include <vector>
#include <atcoder/modint>
#include <atcoder/convolution>

// Represents Polynomial on field F
template <class F, std::vector<F> (*conv)(const std::vector<F> &, const std::vector<F> &)>
class Polynomial
{
    std::vector<F> p;

    // Calculate small inverses
    static F inverse(int v)
    {
        static std::vector<F> inv = {F(0)};

        for (int i = inv.size(); i <= v; i++)
            inv.push_back(1 / F(i));

        return inv[v];
    }

public:
    // Initializes empty polynomial with degree -1
    Polynomial() : p() {}

    // Initializes polynomial using vector.
    // P is represented as v[i]x^i
    Polynomial(std::vector<F> v) : p(v) {}

    // Get degree of Polynomial, zero polynomial has degree -1.
    int deg() const { return (int)p.size() - 1; }

    // Resize polynomial to certain degree
    void set_degree(int deg)
    {
        assert(deg >= -1);
        p.resize(deg + 1);
    }

    F &operator[](int idx)
    {
        return p[idx];
    }

    const F &operator[](int idx) const
    {
        return p[idx];
    }

    // Adds two polynomial, degree is maximum of two operands.
    Polynomial operator+(const Polynomial &rhs) const
    {
        Polynomial ret = *this;
        if (ret.deg() < rhs.deg())
            ret.set_degree(rhs.deg());
        for (int i = 0; i <= rhs.deg(); i++)
            ret[i] += rhs[i];
        return ret;
    }

    Polynomial &operator+=(const Polynomial &rhs)
    {
        if (deg() < rhs.deg())
            set_degree(rhs.deg());
        for (int i = 0; i <= rhs.deg(); i++)
            p[i] += rhs[i];
        return *this;
    }

    // Subtracts two polynomial, degree is maximum of two operands.
    Polynomial operator-(const Polynomial &rhs) const
    {
        Polynomial ret = *this;
        if (ret.deg() < rhs.deg())
            ret.set_degree(rhs.deg());
        for (int i = 0; i <= rhs.deg(); i++)
            ret[i] -= rhs[i];
        return ret;
    }

    Polynomial &operator-=(const Polynomial &rhs)
    {
        if (deg() < rhs.deg())
            set_degree(rhs.deg());
        for (int i = 0; i <= rhs.deg(); i++)
            p[i] -= rhs[i];
        return *this;
    }

    Polynomial operator-() const
    {
        Polynomial ret = *this;
        for (int i = 0; i <= ret.deg(); i++)
            ret[i] = -ret[i];
        return ret;
    }

    Polynomial operator>>(int K) const
    {
        return floordiv_xK(K);
    }

    Polynomial operator<<(int K) const
    {
        return mult_xK(K);
    }

    // Multiplies two polynomial, degree is sum of two operands.
    // With exception that deg(f) = -1 or deg(g) = -1 will give deg(f*g) = -1
    Polynomial operator*(const Polynomial &rhs) const
    {
        return Polynomial(conv(p, rhs.p));
    }

    Polynomial &operator*=(const Polynomial &rhs)
    {
        p = std::move(conv(p, rhs.p));
        return *this;
    }

    // Get inverse of a polynomial, up to specified degree
    // By default, degree is deg(), P[0] must not be 0.
    Polynomial inv(int degree = -1) const
    {
        if (degree == -1)
            degree = deg();
        assert(deg() >= 0 && degree >= 0 && p[0] != F(0));

        Polynomial a({F(1) / p[0]});
        for (int l = 1; l <= degree; l *= 2)
        {
            Polynomial p0 = std::vector(p.begin(), p.begin() + std::min(l, (int)p.size()));
            Polynomial p1;
            if ((int)p.size() >= l)
                p1 = std::vector(p.begin() + l, p.begin() + std::min(2 * l, (int)p.size()));

            Polynomial ap0 = a * p0;
            Polynomial c = std::vector(ap0.p.begin() + l, ap0.p.end());

            Polynomial b = a * p1;
            b.set_degree(l - 1);
            b += c;
            b *= a;
            b.set_degree(l - 1);
            a.p.resize(2 * l);
            for (int i = l; i < 2 * l; i++)
                a.p[i] -= b[i - l];
        }
        a.set_degree(degree);
        return a;
    }

    // Returns int f(x).
    // Returns polynomial with f(0) = 0, degree increases by 1
    Polynomial integ() const
    {
        Polynomial ret;
        ret.set_degree(p.size());

        for (int i = 1; i <= ret.deg(); i++)
            ret[i] = p[i - 1] * inverse(i);
        return ret;
    }

    // Returns f(x)/x^K, truncated.
    Polynomial floordiv_xK(int K) const
    {
        if (deg() < K)
            return {};
        return std::vector(p.begin() + K, p.end());
    }

    // Returns f(x)*x^K
    Polynomial mult_xK(int K) const
    {
        std::vector<F> V(p.size() + K);
        std::copy(p.begin(), p.end(), V.begin() + K);
        return V;
    }

    // Returns df/dx
    // degree decreases by 1
    Polynomial diff() const
    {
        if (deg() <= 0)
            return Polynomial();

        Polynomial ret;
        ret.set_degree(deg() - 1);
        for (int i = 0; i <= ret.deg(); i++)
            ret[i] = (i + 1) * p[i + 1];
        return ret;
    }

    // Returns ln(f(x)) where f(0) = 1, up to degree
    // By default, degree is deg(), P[0] must be 1.
    Polynomial ln(int degree = -1) const
    {
        if (degree == -1)
            degree = deg();
        if (degree == 0)
            return Polynomial({F(0)});
        assert(degree >= 0 && deg() >= 0 && p[0] == 1);

        Polynomial integrand = diff() * inv(degree - 1);
        integrand.set_degree(degree - 1);
        return integrand.integ();
    }

    // Returns exp(f(x)) where f(0) = 0, up to degree
    // By default, degree is deg(), P[0] must not be 0.
    Polynomial exp(int degree = -1) const
    {
        if (degree == -1)
            degree = deg();
        if (degree == 0)
            return Polynomial({F(1)});
        assert(degree >= 0 && deg() >= 0 && p[0] == F(0));

        Polynomial h({F(1)});
        for (int l = 1; l <= degree; l *= 2)
        {
            Polynomial m = std::vector(p.begin(), p.begin() + std::min(2 * l, (int)p.size()));
            m -= h.ln(2 * l);
            m[0] += F(1);
            h *= m;
            h.set_degree(2 * l);
        }
        h.set_degree(degree);
        return h;
    }

    // Returns f(x+a)
    Polynomial taylor_shift(F a) const
    {
        if (deg() <= 0)
            return *this;

        std::vector<F> fact(deg() + 1);
        fact[0] = F(1);
        for (int i = 1; i <= deg(); i++)
            fact[i] = F(i) * fact[i - 1];

        std::vector<F> f(deg() + 1), g(deg() + 1);

        F cur = F(1);
        for (int i = 0; i <= deg(); i++)
        {
            f[i] = p[i] * fact[i];
            cur *= F(i + 1);
        }

        cur = F(1);
        for (int i = 0; i <= deg(); i++)
        {
            g[i] = cur;
            cur *= a * F(i + 1);
        }
        reverse(g.begin(), g.end());

        std::vector<F> res = conv(f, g);
        res.erase(res.begin(), res.begin() + deg());
        for (int i = 0; i <= deg(); i++)
            res[i] /= fact[i];

        return Polynomial(res);
    }
};
using Mint = atcoder::modint998244353;
using Poly = Polynomial<Mint, atcoder::convolution>;

#include <iostream>
using namespace std;

int main()
{
    int N, K;
    scanf("%d%d", &N, &K);
    vector<Mint> ev(N + 1);

    int f = -1;
    for (int i = 1; i <= N; i++)
    {
        int t;
        cin >> t;
        ev[i] = t;
        if (t != 0 && f == -1)
            f = i;
    }

    Poly E = ev;
    auto P = (Poly({1}) - E).inv() - Poly({1});

    if (K > 0)
    {
        Poly E_ = (E.diff() >> (f - 1)).inv() * E;
        for (int i = 0; i < K; i++)
            P = (P.diff() >> (f - 1)) * E_;
    }
    else if (K < 0)
    {
        Poly E_ = E.diff() * (E >> f).inv();
        for (int i = 0; i < -K; i++)
            P = ((P * E_) >> f).integ();
    }

    for (int i = 1; i <= N; i++)
        cout << P[i].val() << " ";
    cout << endl;
}
0