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

• 問題: No.2556 Increasing Matrix
• ユーザー: suisen
• 提出日時: 2023-12-02 01:50:48
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 323 ms / 6,000 ms
• コード長: 4,830 bytes
• コンパイル時間: 2,724 ms
• コンパイル使用メモリ: 127,220 KB
• 実行使用メモリ: 33,672 KB
• 最終ジャッジ日時: 2024-09-26 16:14:11
• 合計ジャッジ時間: 4,929 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
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	2 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	3 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	5 ms; 5,376 KB
testcase_14	AC	9 ms; 5,376 KB
testcase_15	AC	8 ms; 5,376 KB
testcase_16	AC	8 ms; 5,376 KB
testcase_17	AC	16 ms; 5,376 KB
testcase_18	AC	154 ms; 18,808 KB
testcase_19	AC	316 ms; 33,184 KB
testcase_20	AC	312 ms; 33,104 KB
testcase_21	AC	150 ms; 18,596 KB
testcase_22	AC	16 ms; 5,376 KB
testcase_23	AC	313 ms; 33,672 KB
testcase_24	AC	323 ms; 33,672 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);

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

    int z = 1;
    while (z < siz_a) z <<= 1;

    polynomial a2 = a, b2(b.rbegin(), b.rend());
    a2.resize(z);
    b2.resize(z);
    atcoder::internal::butterfly(a2);
    atcoder::internal::butterfly(b2);
    mint iz = mint(z).inv();
    for (int i = 0; i < z; ++i) {
        a2[i] *= b2[i] * iz;
    }
    atcoder::internal::butterfly_inv(a2);
    a2.resize(siz_a);
    a2.erase(a2.begin(), a2.begin() + siz_b - 1);
    return a2;
}

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

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