QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#93892 | #6196. Minimum Element Problem | whatever# | TL | 14ms | 20960kb | C++17 | 4.6kb | 2023-04-03 17:46:16 | 2023-04-03 17:46:20 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
using namespace std;
using i64 = long long;
const int P = 998244353;
template<class T>
inline T power(T a, i64 b) {
T res = 1;
for (; b; b >>= 1, a *= a)
if (b & 1) res *= a;
return res;
}
struct Z {
int x;
Z(int _x = 0) : x(_x) {}
inline Z operator-() const {
if (!x) return 0;
return Z(P - x);
}
inline Z &operator+=(const Z &rhs) {
x += rhs.x;
if (x > P) x -= P;
return *this;
}
inline Z &operator-=(const Z &rhs) {
x -= rhs.x;
if (x < 0) x += P;
return *this;
}
inline Z &operator*=(const Z &rhs) {
x = 1ull * x * rhs.x % P;
return *this;
}
inline Z inv() const {
return power(*this, P - 2);
}
inline Z &operator/=(const Z &rhs) {
*this *= rhs.inv();
return *this;
}
inline Z operator+(const Z &rhs) const {
Z res = *this;
return res += rhs;
}
inline Z operator-(const Z &rhs) const {
Z res = *this;
return res -= rhs;
}
inline Z operator*(const Z &rhs) const {
Z res = *this;
return res *= rhs;
}
inline Z operator/(const Z &rhs) const {
Z res = *this;
return res /= rhs;
}
};
const Z inv2 = (P + 1) / 2;
vector<int> rev;
vector<Z> roots{0, 1};
using poly = vector<Z>;
void dft(poly &a) {
int n = a.size();
if (int(rev.size()) != n) {
rev.resize(n);
int k = __builtin_ctz(n) - 1;
for (int i = 0; i < n; ++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k);
}
for (int i = 0; i < n; ++i)
if (i < rev[i]) swap(a[i], a[rev[i]]);
if (int(roots.size()) < n) {
int k = __builtin_ctz(roots.size());
roots.resize(n);
for (; (1 << k) < n; ++k) {
Z e = power(Z(3), (P - 1) >> (k + 1));
for (int i = 1 << (k - 1); i < (1 << k); ++i) {
roots[i * 2] = roots[i];
roots[i * 2 + 1] = roots[i] * e;
}
}
}
for (int k = 1; k < n; k *= 2) {
for (int i = 0; i < n; i += k * 2) {
for (int j = 0; j < k; ++j) {
Z x = a[i + j];
Z y = a[i + j + k] * roots[k + j];
a[i + j] = x + y;
a[i + j + k] = x - y;
}
}
}
}
void idft(poly &a) {
reverse(a.begin() + 1, a.end());
dft(a);
int n = a.size();
Z inv = Z(n).inv();
for (int i = 0; i < n; ++i)
a[i] *= inv;
}
inline int extend(int len) {
int n = 1;
while (n < len)
n <<= 1;
return n;
}
poly operator*(poly a, poly b) {
if (a.empty() || b.empty()) return poly();
int len = int(a.size() + b.size()) - 1;
int n = extend(len);
a.resize(n), dft(a);
b.resize(n), dft(b);
for (int i = 0; i < n; ++i)
a[i] *= b[i];
idft(a);
a.resize(len);
return a;
}
Z fac[1000011], ifac[1000011], inv[1000011];
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i;
ifac[n] = power(fac[n], P - 2);
for (int i = n - 1; ~i; --i)
ifac[i] = ifac[i + 1] * (i + 1), inv[i] = ifac[i] * fac[i - 1];
}
Z binom(int n, int m) {
return fac[n] * ifac[m] * ifac[n - m];
}
int n, x;
Z C[500005], ans1[500005], ans2[500005];
int main() {
init(1000010);
cin >> n >> x;
rep(i, 0, n) C[i] = binom(2 * i, i) * inv[i + 1];
{
poly f(x), g(n - x + 1);
rep(i, 0, x - 1) f[i] = C[i];
rep(i, 0, n - x) g[i] = C[i];
auto res = f * g;
rep(i, 1, n) ans1[i + 1] = ans1[i] + res[n - i] * C[i - 1];
}
{
auto get = [&](int p) {
poly a(p + 1), b(p + 1);
Z x = inv2, y = 1;
rep(j, 1, p) y *= x, x -= 1;
rep(i, 0, p) {
if (i % 2 == 0) continue;
if (i > 1) {
y *= Z(P - i);
y *= inv[2 * p - i];
}
a[i] = y * ifac[p];
a[i] *= power(Z(P - 4), p);
a[i] *= ifac[i];
if (i & 1) a[i] = -a[i];
}
rep(i, 0, p) b[i] = ifac[i];
auto c = a * b;
poly f(p + 1);
rep(i, 1, p) {
Z val = c[i] * fac[i];
val *= power(inv2, i);
val *= ifac[i - 1];
f[i] = val;
}
return f;
};
auto f = get(x), g = get(n - x + 1);
auto res = f * g;
per(i, n, 1) {
auto cur = res[i + 1] * fac[i - 1];
cerr << "i = " << i << ", cur = " << cur.x << "\n";
ans2[i - 1] = ans2[i] + cur;
}
}
rep(i, 1, n) {
auto res = C[n] - ans1[i] - ans2[i];
cout << res.x << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 20932kb
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: 14ms
memory: 20960kb
input:
10 5
output:
588 1176 2716 4942 7407 9101 9636 9167 7596 4862
result:
ok 10 numbers
Test #3:
score: -100
Time Limit Exceeded
input:
500000 1