QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107802 | #6196. Minimum Element Problem | Narrator | RE | 3ms | 3664kb | C++14 | 5.5kb | 2023-05-22 20:56:17 | 2023-05-22 20:56:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
inline void add(int &x, const int y) {(x += y) >= mod && (x -= mod);}
inline int Add(int x, const int y) {return add(x, y), x;}
inline void sub(int &x, const int y) {(x -= y) < 0 && (x += mod);}
inline int Sub(int x, const int y) {return sub(x, y), x;}
inline void mul(int &x, const int y) {x = 1ll * x * y % mod;}
inline int Mul(const int x, const int y) {return 1ll * x * y % mod;}
inline int power(int a, int b, int c = 1) {
for (; b; b >>= 1, mul(a, a))
if (b & 1) mul(c, a);
return c;
}
const int N = (1 << 18) + 5;
int inv[N], fac[N], ifac[N];
inline void init(int n) {
for (int i = 0; i < 2; ++i) inv[i] = fac[i] = ifac[i] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = Mul(mod - mod / i, inv[mod % i]);
fac[i] = Mul(fac[i - 1], i);
ifac[i] = Mul(ifac[i - 1], inv[i]);
}
}
inline int binom(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return Mul(fac[n], Mul(ifac[m], ifac[n - m]));
}
typedef std::vector<int> poly;
inline void read(poly &a, int n) { a.resize(n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]);}
inline void print(const poly &a) {for (int i = 0; i < a.size(); ++i) printf("%d%c", a[i], i == a.size() - 1 ? '\n' : ' ');}
poly operator <<= (poly &a, const int &x) {
a.resize(a.size() + x);
for (int i = a.size() - 1; i >= x; --i) a[i] = a[i - x];
return std::fill(a.begin(), a.begin() + x, 0), a;
}
poly operator << (const poly &a, const int &x) {poly ans(a); return ans <<= x, ans;}
poly operator += (poly &a, const poly &b) {
if (a.size() < b.size()) a.resize(b.size());
for (int i = 0; i < b.size(); ++i) add(a[i], b[i]);
return a;
}
poly operator + (const poly &a, const poly &b) {poly c(a); c += b; return c;}
poly operator -= (poly &a, const poly &b) {
if (a.size() < b.size()) a.resize(b.size());
for (int i = 0; i < b.size(); ++i) sub(a[i], b[i]);
return a;
}
poly operator - (const poly &a, const poly &b) {poly c(a); c -= b; return c;}
poly operator - (const poly &a) {poly ans(a); for (auto &x : ans) x = mod - x; return ans;}
poly toEGF(poly &a) {for (int i = 0; i < a.size(); ++i) mul(a[i], ifac[i]); return a;}
void dft(int *a, int n) {
for (int i = 0, j = 0; i < n; ++i) {
if (i < j) std::swap(a[i], a[j]);
for (int k = n >> 1; (j ^= k) < k; k >>= 1);
}
for (int k = 1, m = 2; k < n; k <<= 1, m <<= 1) {
int wn = power(3, (mod - 1) / m);
for (int i = 0; i < n; i += m)
for (int j = 0, w = 1; j < k; ++j, mul(w, wn)) {
int tmp = Mul(a[i + j + k], w);
a[i + j + k] = Sub(a[i + j], tmp);
add(a[i + j], tmp);
}
}
}
void idft(int *a, int n) {
std::reverse(a + 1, a + n), dft(a, n);
int coef = power(n, mod - 2);
for (int i = 0; i < n; ++i) mul(a[i], coef);
}
int extend(int x) {int n = 1; while (n < x) n <<= 1; return n;}
poly operator * (const poly &a, const poly &b) {
int len = a.size() + b.size() - 1;
int n = extend(len);
static int x[N], y[N], z[N];
for (int i = 0; i < n; ++i) x[i] = i < a.size() ? a[i] : 0, y[i] = i < b.size() ? b[i] : 0;
dft(x, n), dft(y, n);
for (int i = 0; i < n; ++i) z[i] = Mul(x[i], y[i]);
idft(z, n); poly c(len);
for (int i = 0; i < len; ++i) c[i] = z[i];
return c;
}
poly operator *= (poly &a, const poly &b) {return a = a * b;}
poly operator *= (poly &a, const int &b) {for (auto &x : a) mul(x, b); return a;}
poly operator * (poly a, const int &b) {return a *= b;}
poly operator * (const int &b, poly a) {return a *= b;}
poly _inv(const poly &a) {
int len = a.size();
if (len == 1) return {power(a[0], mod - 2)};
poly b(_inv({a.begin(), a.begin() + len / 2})), c(a * b), ans(b);
c = poly{c.begin() + len / 2, c.end()} * b, ans.resize(len);
for (int i = 0; i < len / 2; ++i) if (c[i]) ans[len / 2 + i] = mod - c[i];
return ans;
}
poly Inv(poly a) {
int len = a.size(); a.resize(extend(len));
poly ans(_inv(a)); ans.resize(len);
return ans;
}
poly Deri(poly a) {
for (int i = 0; i < a.size() - 1; ++i) a[i] = Mul(i + 1, a[i + 1]);
return a.pop_back(), a;
}
poly Inte(poly a) {
a.resize(a.size() + 1);
for (int i = a.size() - 1; i; --i) a[i] = Mul(a[i - 1], inv[i]);
return a[0] = 0, a;
}
poly Ln(poly a) {
poly ans(Inte(Deri(a) * Inv(a)));
return ans.resize(a.size()), ans;
}
poly _exp(const poly &a) {
int len = a.size();
if (len == 1) return {1};
poly b(_exp({a.begin(), a.begin() + len / 2})); b.resize(len);
poly ans(a - Ln(b)); add(ans[0], 1), b.resize(len / 2);
return ans *= b, ans.resize(len), ans;
}
poly Exp(poly a) {
int len = a.size(); a.resize(extend(len));
poly ans(_exp(a)); ans.resize(len);
return ans;
}
int n, x, ans[N];
poly F;
int G(int k, int n)
{
return (ll)(k + 1) * inv[n + k + 1] % mod * binom(2 * n + k, n) % mod;
}
int main()
{
scanf("%d%d", &n, &x);
init(n << 1);
F.emplace_back(1);
for (int i = 1; i <= n; i++)
F.emplace_back((ll)binom(2 * i, i) * inv[i + 1] % mod);
poly P(F.begin(), F.begin() + x);
poly Q(F.begin(), F.begin() + n - x + 1);
P = P * Q;
for (int i = 0; i < n; i++)
ans[n - i] = (ans[n - i] + (ll)(mod - P[i]) * F[n - i - 1]) % mod;
P.resize(x);
for (int i = 0; i < x; i++)
P[i] = (ll)ifac[i] * G(i, x - 1 - i) % mod;
for (int i = 0; i <= n - x; i++)
Q[i] = (ll)ifac[i] * G(i, n - x - i) % mod;
P = P * Q;
assert((int)P.size() == n);
for (int i = 0; i < n; i++)
ans[i] = (ans[i] + (ll)P[i] * fac[i]) % mod;
for (int i = 1; i < n; i++)
(ans[i] += ans[i - 1]) %= mod;
for (int i = 0; i < n; i++)
printf("%d\n", ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3664kb
input:
5 2
output:
5 10 16 20 14
result:
ok 5 number(s): "5 10 16 20 14"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3604kb
input:
10 5
output:
588 1176 2716 4942 7407 9101 9636 9167 7596 4862
result:
ok 10 numbers
Test #3:
score: -100
Runtime Error
input:
500000 1