結果

問題 No.2556 Increasing Matrix
ユーザー suisen
提出日時 2023-12-02 01:22:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 514 ms / 6,000 ms
コード長 4,538 bytes
コンパイル時間 4,347 ms
コンパイル使用メモリ 122,128 KB
最終ジャッジ日時 2025-02-18 03:12:47
ジャッジサーバーID
(参考情報)
judge4 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
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])
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];
}
auto 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0