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

• 問題: No.2556 Increasing Matrix
• ユーザー: suisen
• 提出日時: 2023-12-02 01:07:00
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 592 ms / 6,000 ms
• コード長: 5,454 bytes
• コンパイル時間: 3,193 ms
• コンパイル使用メモリ: 133,116 KB
• 実行使用メモリ: 45,704 KB
• 最終ジャッジ日時: 2024-09-26 16:09:59
• 合計ジャッジ時間: 7,221 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	2 ms; 6,944 KB
testcase_06	AC	2 ms; 6,944 KB
testcase_07	AC	2 ms; 6,940 KB
testcase_08	AC	3 ms; 6,940 KB
testcase_09	AC	4 ms; 6,940 KB
testcase_10	AC	3 ms; 6,944 KB
testcase_11	AC	3 ms; 6,940 KB
testcase_12	AC	3 ms; 6,940 KB
testcase_13	AC	7 ms; 6,940 KB
testcase_14	AC	14 ms; 6,944 KB
testcase_15	AC	13 ms; 6,940 KB
testcase_16	AC	13 ms; 6,944 KB
testcase_17	AC	25 ms; 6,940 KB
testcase_18	AC	280 ms; 23,728 KB
testcase_19	AC	541 ms; 44,032 KB
testcase_20	AC	547 ms; 44,272 KB
testcase_21	AC	273 ms; 23,408 KB
testcase_22	AC	27 ms; 6,944 KB
testcase_23	AC	592 ms; 45,704 KB
testcase_24	AC	591 ms; 45,700 KB

ソースコード

#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();
    if (siz_f < siz_g) return g * f;
    if (std::min(siz_f, siz_g) <= 60) return atcoder::convolution(f, g);
    const int deg = siz_f + siz_g - 2;
    int fpow2 = 1;
    while ((fpow2 << 1) <= deg) fpow2 <<= 1;
    if (const int dif = deg - fpow2 + 1; dif <= 10) {
        polynomial h = atcoder::convolution(std::vector<mint>(f.begin(), f.end() - dif), g);
        h.resize(h.size() + dif);
        for (int i = siz_f - dif; i < siz_f; ++i) for (int j = 0; j < siz_g; ++j) {
            h[i + j] += f[i] * g[j];
        }
        return h;
    }
    return atcoder::convolution(f, g);
}

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

polynomial middle_product(const polynomial& a, const polynomial& 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) {
        polynomial 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;
    }
    polynomial res = a * polynomial(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;
}