結果

問題 No.1985 [Cherry 4th Tune] Early Summer Rain
ユーザー colognecologne
提出日時 2022-05-03 13:46:45
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4,929 ms / 7,000 ms
コード長 10,984 bytes
コンパイル時間 3,826 ms
コンパイル使用メモリ 168,256 KB
実行使用メモリ 113,076 KB
最終ジャッジ日時 2024-06-02 06:03:18
合計ジャッジ時間 104,458 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 84 ms
8,480 KB
testcase_15 AC 494 ms
22,752 KB
testcase_16 AC 1,510 ms
51,520 KB
testcase_17 AC 36 ms
6,044 KB
testcase_18 AC 321 ms
25,036 KB
testcase_19 AC 2,097 ms
79,352 KB
testcase_20 AC 214 ms
14,592 KB
testcase_21 AC 2,110 ms
80,764 KB
testcase_22 AC 1,081 ms
43,620 KB
testcase_23 AC 8 ms
5,376 KB
testcase_24 AC 4,890 ms
112,952 KB
testcase_25 AC 4,927 ms
113,076 KB
testcase_26 AC 4,859 ms
112,948 KB
testcase_27 AC 4,889 ms
112,944 KB
testcase_28 AC 4,411 ms
111,560 KB
testcase_29 AC 4,825 ms
112,948 KB
testcase_30 AC 4,229 ms
111,564 KB
testcase_31 AC 4,334 ms
111,560 KB
testcase_32 AC 4,308 ms
111,560 KB
testcase_33 AC 4,929 ms
112,944 KB
testcase_34 AC 4,910 ms
113,064 KB
testcase_35 AC 4,305 ms
111,560 KB
testcase_36 AC 4,752 ms
112,948 KB
testcase_37 AC 4,820 ms
112,948 KB
testcase_38 AC 4,246 ms
111,560 KB
testcase_39 AC 2 ms
5,376 KB
testcase_40 AC 65 ms
8,044 KB
testcase_41 AC 359 ms
8,592 KB
testcase_42 AC 4,307 ms
110,796 KB
testcase_43 AC 4,856 ms
112,224 KB
testcase_44 AC 4,312 ms
111,556 KB
testcase_45 AC 4,764 ms
112,948 KB
testcase_46 AC 67 ms
8,128 KB
testcase_47 AC 361 ms
8,588 KB
権限があれば一括ダウンロードができます

ソースコード

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 <cassert>
#include <cstdio>
#include <cinttypes>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
class StrictInput
{
    char *p;
    off_t cur = 0;
    off_t len = 0;

public:
    explicit StrictInput(int fd = 0)
    {
        struct stat st;
        fstat(fd, &st);
        p = (char *)mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
        len = st.st_size;
    }

    char readChar()
    {
        assert(cur != len);
        return p[cur++];
    }

    void unreadChar()
    {
        assert(cur != 0);
        --cur;
    }

    bool isEof() { return cur == len; }
    void readEof() { assert(isEof()); }
    void readSpace() { assert(readChar() == ' '); }
    void readEoln() { assert(readChar() == '\n'); }

    // reads uint64_t in range [from, to]
    uint64_t readU64(uint64_t from = 0, uint64_t to = UINT64_MAX)
    {
        uint64_t cur = 0;
        off_t read_cnt = 0;
        bool leading_zero = false;
        while (!isEof())
        {
            char p = readChar();
            if (!('0' <= p && p <= '9'))
            {
                unreadChar();
                break;
            }
            uint64_t v = p - '0';
            assert(cur <= UINT64_MAX / 10);
            cur *= 10;
            assert(cur <= UINT64_MAX - v);
            cur += v;
            if (read_cnt == 0 && v == 0)
                leading_zero = true;
            ++read_cnt;
        }
        if (cur == 0)
            assert(read_cnt == 1);
        else
            assert(!leading_zero);
        assert(from <= cur && cur <= to);
        return cur;
    }

    // reads int64_t in range [from, to]
    int64_t readI64(int64_t from = INT64_MIN, int64_t to = INT64_MAX)
    {
        uint64_t cur = 0;
        off_t read_cnt = 0;
        bool leading_zero = false;
        bool leading_minus = readChar() == '-';
        if (!leading_minus)
            unreadChar();
        while (!isEof())
        {
            char p = readChar();
            if (!('0' <= p && p <= '9'))
            {
                unreadChar();
                break;
            }
            uint64_t v = p - '0';
            assert(cur <= UINT64_MAX / 10);
            cur *= 10;
            assert(cur <= UINT64_MAX - v);
            cur += v;
            if (read_cnt == 0 && v == 0)
                leading_zero = true;
            ++read_cnt;
        }
        if (cur == 0)
            assert(read_cnt == 1 && !leading_minus);
        else
            assert(!leading_zero);

        if (cur <= INT64_MAX)
        {
            int64_t ret = cur;
            if (leading_minus)
                ret = -ret;
            assert(from <= ret && ret <= to);
            return ret;
        }
        else
        {
            assert(leading_minus && cur == uint64_t(INT64_MIN));
            assert(from == INT64_MIN);
            return INT64_MIN;
        }
    }
};

#include <iostream>
using namespace std;

int main()
{
    int N, K;
    StrictInput inf;
    N = inf.readU64(1, 100'000);
    inf.readSpace();
    K = inf.readI64(-20, 20);
    inf.readEoln();
    vector<Mint> ev(N + 1);

    int f = -1;
    for (int i = 1; i <= N; i++)
    {
        int t = inf.readU64(0, 998'244'353);
        ev[i] = t;
        if (t != 0 && f == -1)
            f = i;
        if (i == N)
            inf.readEoln();
        else
            inf.readSpace();
    }

    inf.readEof();

    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