#757893 (C++23) No.1985 [Cherry 4th Tune] Early Summer Rain

提出ソース

結果

問題	No.1985 [Cherry 4th Tune] Early Summer Rain
ユーザー	👑 cologne
提出日時	2022-05-03 13:46:45
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	5,185 ms / 7,000 ms
コード長	10,984 bytes
コンパイル時間	4,889 ms
コンパイル使用メモリ	169,536 KB
実行使用メモリ	112,900 KB
最終ジャッジ日時	2023-08-24 16:02:10
合計ジャッジ時間	113,846 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	4 ms 4,376 KB
testcase_07	AC	3 ms 4,380 KB
testcase_08	AC	3 ms 4,376 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	3 ms 4,376 KB
testcase_11	AC	4 ms 4,376 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	95 ms 8,268 KB
testcase_15	AC	532 ms 22,500 KB
testcase_16	AC	1,608 ms 53,104 KB
testcase_17	AC	38 ms 5,620 KB
testcase_18	AC	349 ms 24,860 KB
testcase_19	AC	2,247 ms 79,216 KB
testcase_20	AC	229 ms 14,272 KB
testcase_21	AC	2,232 ms 80,856 KB
testcase_22	AC	1,130 ms 43,400 KB
testcase_23	AC	8 ms 4,380 KB
testcase_24	AC	5,185 ms 112,588 KB
testcase_25	AC	5,179 ms 112,812 KB
testcase_26	AC	5,164 ms 112,652 KB
testcase_27	AC	5,149 ms 112,840 KB
testcase_28	AC	4,501 ms 112,076 KB
testcase_29	AC	5,181 ms 112,604 KB
testcase_30	AC	4,509 ms 112,504 KB
testcase_31	AC	4,540 ms 112,804 KB
testcase_32	AC	4,516 ms 111,484 KB
testcase_33	AC	5,149 ms 112,624 KB
testcase_34	AC	5,154 ms 112,732 KB
testcase_35	AC	4,494 ms 112,288 KB
testcase_36	AC	5,169 ms 112,900 KB
testcase_37	AC	5,169 ms 112,788 KB
testcase_38	AC	4,510 ms 111,680 KB
testcase_39	AC	2 ms 4,380 KB
testcase_40	AC	70 ms 7,908 KB
testcase_41	AC	388 ms 8,304 KB
testcase_42	AC	4,512 ms 111,376 KB
testcase_43	AC	5,174 ms 111,828 KB
testcase_44	AC	4,531 ms 111,444 KB
testcase_45	AC	5,180 ms 112,812 KB
testcase_46	AC	69 ms 7,928 KB
testcase_47	AC	388 ms 8,392 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード