#933350 (C++17) No.2556 Increasing Matrix

提出ソース

結果

問題	No.2556 Increasing Matrix
ユーザー	suisen
提出日時	2023-12-02 01:00:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	712 ms / 6,000 ms
コード長	6,295 bytes
コンパイル時間	3,157 ms
コンパイル使用メモリ	134,120 KB
実行使用メモリ	45,828 KB
最終ジャッジ日時	2024-09-26 16:08:42
合計ジャッジ時間	7,545 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	4 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	7 ms 5,376 KB
testcase_14	AC	15 ms 5,376 KB
testcase_15	AC	15 ms 5,376 KB
testcase_16	AC	15 ms 5,376 KB
testcase_17	AC	28 ms 5,376 KB
testcase_18	AC	340 ms 23,748 KB
testcase_19	AC	646 ms 44,344 KB
testcase_20	AC	655 ms 44,348 KB
testcase_21	AC	325 ms 23,388 KB
testcase_22	AC	31 ms 5,376 KB
testcase_23	AC	708 ms 45,580 KB
testcase_24	AC	712 ms 45,828 KB

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

ソースコード

raw source code

#include <deque>
#include <iostream>
#include <vector>

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

using mint = atcoder::modint998244353;

using polynomial = std::vector<mint>;

using formal_power_series = std::vector<mint>;

formal_power_series fps_inv(const formal_power_series& f, int n) {
    assert(f.size() and f[0] != 0);
    formal_power_series g{ f[0].inv() };
    for (int k = 1; k < n; k *= 2) {
        std::vector<mint> f_fft(f.begin(), f.begin() + std::min<int>(2 * k, f.size()));
        std::vector<mint> g_fft(g.begin(), g.end());

        f_fft.resize(2 * k);
        g_fft.resize(2 * k);

        atcoder::internal::butterfly(f_fft);
        atcoder::internal::butterfly(g_fft);

        std::vector<mint> fg(2 * k);
        for (int i = 0; i < 2 * k; ++i) {
            fg[i] = f_fft[i] * g_fft[i];
        }
        atcoder::internal::butterfly_inv(fg);
        fg.erase(fg.begin(), fg.begin() + k);
        fg.resize(2 * k);
        atcoder::internal::butterfly(fg);
        for (int i = 0; i < 2 * k; ++i) {
            fg[i] *= g_fft[i];
        }
        atcoder::internal::butterfly_inv(fg);
        const mint iz = mint(2 * k).inv(), c = -iz * iz;
        g.resize(2 * k);
        for (int i = 0; i < k; ++i) {
            g[k + i] = fg[i] * c;
        }
    }
    g.resize(n);
    return g;
}

polynomial operator+(const polynomial& f, const polynomial& g) {
    const int siz_f = f.size(), siz_g = g.size();
    polynomial res = f;
    if (siz_f < siz_g) {
        res.resize(siz_g);
    }
    for (int i = 0; i < siz_g; ++i) {
        res[i] += g[i];
    }
    return res;
}
polynomial operator-(const polynomial& f, const polynomial& g) {
    const int siz_f = f.size(), siz_g = g.size();
    polynomial res = f;
    if (siz_f < siz_g) {
        res.resize(siz_g);
    }
    for (int i = 0; i < siz_g; ++i) {
        res[i] -= g[i];
    }
    return res;
}
polynomial operator*(const polynomial& f, const polynomial& g) {
    return atcoder::convolution(f, g);
}
polynomial operator/(polynomial f, polynomial g) {
    while (f.size() and f.back() == 0) f.pop_back();
    while (g.size() and g.back() == 0) g.pop_back();
    const int fd = f.size() - 1, gd = g.size() - 1;
    assert(gd >= 0);
    if (fd < gd) {
        return {};
    }
    if (gd == 0) {
        mint inv_g0 = g[0].inv();
        for (auto&& e : f) e *= inv_g0;
        return f;
    }
    std::reverse(f.begin(), f.end());
    std::reverse(g.begin(), g.end());
    const int qd = fd - gd;
    f.resize(qd + 1);
    polynomial q = f * fps_inv(g, qd + 1);
    q.resize(qd + 1);
    std::reverse(q.begin(), q.end());
    return q;
}
polynomial operator%(const polynomial& f, const polynomial& g) {
    polynomial q = f / g, r = f - g * q;
    while (r.size() and r.back() == 0) r.pop_back();
    return r;
}

mint eval(const polynomial& f, const mint& x) {
    const int n = f.size();
    mint y = 0;
    for (int i = n - 1; i >= 0; --i) {
        y = uint64_t(y.val()) * x.val() + f[i].val();
    }
    return y;
}

std::vector<mint> middle_product(const std::vector<mint>& a, const std::vector<mint>& b) {
    const int siz_a = a.size(), siz_b = b.size();
    assert(siz_a >= siz_b and siz_b);
    if (std::min(siz_b, siz_a - siz_b + 1) <= 60) {
        std::vector<mint> res(siz_a - siz_b + 1);
        for (int i = 0; i <= siz_a - siz_b; ++i) {
            for (int j = 0; j < siz_b; ++j) {
                res[i] += b[j] * a[i + j];
            }
        }
        return res;
    }
    std::vector<mint> res = atcoder::convolution(a, std::vector<mint>(b.rbegin(), b.rend()));
    res.resize(siz_a);
    res.erase(res.begin(), res.begin() + siz_b - 1);
    return res;
}

std::vector<mint> multipoint_evaluation(const polynomial& f, const std::vector<mint> &xs) {
    const int n = f.size(), m = xs.size();

    if (m == 0) {
        return {};
    }
    if (f.size() <= 60) {
        std::vector<mint> ys(n);
        for (int i = 0; i < n; ++i) {
            ys[i] = eval(f, xs[i]);
        }
        return ys;
    }

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

    std::vector<std::vector<mint>> t(2 * k);
    for (int i = 0; i < m; ++i) {
        t[k + i] = { 1, -xs[i] };
    }
    for (int i = m; i < k; ++i) {
        t[k + i] = { 1, 0 };
    }
    for (int i = k - 1; i; --i) {
        t[i] = t[2 * i] * t[2 * i + 1];
    }
    polynomial f2 = f;
    f2.resize(2 * n - 1);
    t[1] = middle_product(f2, fps_inv(t[1], n));
    t[1].resize(k);
    for (int i = 1; i < k; ++i) {
        std::vector<mint> tr = middle_product(t[i], t[2 * i + 0]);
        std::vector<mint> tl = middle_product(t[i], t[2 * i + 1]);
        t[2 * i + 0] = std::move(tl);
        t[2 * i + 1] = std::move(tr);
    }
    std::vector<mint> ys(m);
    for (int i = 0; i < m; ++i) {
        ys[i] = t[k + i].empty() ? 0 : t[k + i].front();
    }
    return ys;
}

std::vector<mint> product_of_differences(const std::vector<mint>& xs) {
    // f(x):=Π_i(x-x[i])
    // => f'(x)=Σ_i Π[j!=i](x-x[j])
    // => f'(x[i])=Π[j!=i](x[i]-x[j])
    const int n = xs.size();
    std::deque<polynomial> dq;
    for (int i = 0; i < n; ++i) dq.push_back(polynomial{ -xs[i], 1 });
    while (dq.size() >= 2) {
        auto f = std::move(dq.front());
        dq.pop_front();
        auto g = std::move(dq.front());
        dq.pop_front();
        dq.push_back(f * g);
    }
    auto f = std::move(dq.front());
    for (int i = 0; i < n; ++i) {
        f[i] = f[i + 1] * (i + 1);
    }
    f.pop_back();
    return multipoint_evaluation(f, xs);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    --n;

    std::vector<int> d(n);
    {
        int p;
        std::cin >> p;
        for (int i = 0; i < n; ++i) {
            int v;
            std::cin >> v;
            d[i] = v - p + 1;
            p = v;
        }
    }
    std::vector<mint> sd(n + 1);
    for (int i = 0; i < n; ++i) {
        sd[i + 1] = sd[i] + d[i];
    }

    auto res = product_of_differences(sd);

    mint ans = mint(-1).pow(1LL * (n + 1) * n / 2);
    for (mint e : res) {
        ans *= e;
    }

    mint fac = 1, facfac = 1;
    for (int i = 1; i <= n; ++i) {
        fac *= i;
        facfac *= fac;
    }
    std::cout << (ans / facfac.pow(2)).val() << std::endl;
}

yukicoder

結果

テストケース

ソースコード