結果

問題 No.1985 [Cherry 4th Tune] Early Summer Rain
ユーザー colognecologne
提出日時 2022-04-27 19:46:50
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 7,496 bytes
コンパイル時間 3,180 ms
コンパイル使用メモリ 151,408 KB
実行使用メモリ 89,204 KB
最終ジャッジ日時 2024-10-09 06:39:50
合計ジャッジ時間 28,402 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 5 ms
5,248 KB
testcase_07 AC 4 ms
5,248 KB
testcase_08 AC 5 ms
5,248 KB
testcase_09 AC 3 ms
5,248 KB
testcase_10 AC 4 ms
5,248 KB
testcase_11 AC 4 ms
5,248 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 105 ms
8,488 KB
testcase_15 AC 1,030 ms
19,084 KB
testcase_16 AC 3,203 ms
45,720 KB
testcase_17 AC 52 ms
6,048 KB
testcase_18 AC 382 ms
24,968 KB
testcase_19 AC 4,480 ms
62,276 KB
testcase_20 AC 296 ms
11,148 KB
testcase_21 AC 4,343 ms
60,744 KB
testcase_22 AC 1,203 ms
43,632 KB
testcase_23 AC 12 ms
5,248 KB
testcase_24 TLE -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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] / F(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);
        for (int i = 0; i <= deg(); i++)
            f[i] = p[i] * fact[i];

        F a_i = 1;
        for (int i = 0; i <= deg(); i++)
        {
            g[i] = a_i / fact[i];
            a_i *= a;
        }
        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