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

• 問題: No.2556 Increasing Matrix
• ユーザー: suisen
• 提出日時: 2023-12-02 01:41:25
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 366 ms / 6,000 ms
• コード長: 5,221 bytes
• コンパイル時間: 3,017 ms
• コンパイル使用メモリ: 127,696 KB
• 実行使用メモリ: 35,720 KB
• 最終ジャッジ日時: 2024-09-26 16:14:06
• 合計ジャッジ時間: 5,535 ms
• ジャッジサーバーID （参考情報）: judge2 / 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	2 ms; 5,376 KB
testcase_08	AC	3 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	5 ms; 5,376 KB
testcase_14	AC	10 ms; 5,376 KB
testcase_15	AC	10 ms; 5,376 KB
testcase_16	AC	9 ms; 5,376 KB
testcase_17	AC	17 ms; 5,376 KB
testcase_18	AC	171 ms; 19,708 KB
testcase_19	AC	338 ms; 32,188 KB
testcase_20	AC	342 ms; 32,304 KB
testcase_21	AC	170 ms; 19,612 KB
testcase_22	AC	19 ms; 5,376 KB
testcase_23	AC	366 ms; 35,592 KB
testcase_24	AC	365 ms; 35,720 KB

ソースコード

#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(polynomial(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);
}

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);
    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> 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])

    auto middle_product_pow2 = [](const polynomial& a, const polynomial& b) {
        const int siz_a = a.size(), siz_b = b.size();
        assert(siz_a >= siz_b and siz_b);
        assert((-siz_a & siz_a) == siz_a);
        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 a2 = a, b2(b.rbegin(), b.rend());
        b2.resize(siz_a);
        atcoder::internal::butterfly(a2);
        atcoder::internal::butterfly(b2);
        mint iz = mint(siz_a).inv();
        for (int i = 0; i < siz_a; ++i) {
            a2[i] *= b2[i] * iz;
        }
        atcoder::internal::butterfly_inv(a2);
        a2.erase(a2.begin(), a2.begin() + siz_b - 1);

        return a2;
    };
    
    const int n = xs.size();

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

    std::vector<std::vector<mint>> t(2 * k);
    for (int i = 0; i < n; ++i) {
        t[k + i] = { 1, -xs[i] };
    }
    for (int i = n; 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 f = t[1];
    f.resize(n + 1);
    std::reverse(f.begin(), f.end());
    for (int i = 0; i < n; ++i) {
        f[i] = f[i + 1] * (i + 1);
    }
    f.resize(n);
    f.resize(2 * n - 1);
    t[1] = middle_product(f, fps_inv(t[1], n));
    t[1].resize(k);
    for (int i = 1; i < k; ++i) {
        std::vector<mint> tr = middle_product_pow2(t[i], t[2 * i + 0]);
        std::vector<mint> tl = middle_product_pow2(t[i], t[2 * i + 1]);
        t[2 * i + 0] = std::move(tl);
        t[2 * i + 1] = std::move(tr);
    }
    std::vector<mint> ys(n);
    for (int i = 0; i < n; ++i) {
        ys[i] = t[k + i].empty() ? 0 : t[k + i].front();
    }
    return ys;
}

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

    mint ans = mint(-1).pow(1LL * (n + 1) * n / 2);
    for (mint e : product_of_differences(sd)) {
        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;
}