QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107555 | #6196. Minimum Element Problem | FISHER_ | RE | 3ms | 3672kb | C++14 | 3.1kb | 2023-05-21 22:59:20 | 2023-05-21 22:59:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int rt = 3, mod = 998244353;
inline int Mod(int x) { return x + ((x >> 31) & mod); }
inline int add(int x, int y) { return Mod(x + y - mod); }
inline int sub(int x, int y) { return Mod(x - y); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
int qpow(int a, int b) {
if (!b) return 1;
int t = qpow(a, b >> 1);
t = mul(t, t);
if (b & 1) return mul(t, a);
return t;
}
const int maxn = 500000;
int fac[maxn + 5], ifac[maxn + 5];
int inv[maxn + 5];
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = mul(fac[i - 1], i);
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; i--) ifac[i] = mul(ifac[i + 1], i + 1);
for (int i = 1; i <= n; i++) inv[i] = mul(ifac[i], fac[i - 1]);
}
inline int C(int m, int n) { return mul(fac[m], mul(ifac[n], ifac[m - n])); }
namespace polynomial {
typedef vector<int> poly;
int rev[4 * maxn + 5];
inline void change(int len, int cnt) {
for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1));
}
void ntt(poly& a, int len, bool type) {
for (int i = 0; i < len; i++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int mid = 1; mid < len; mid <<= 1) {
int r = mid << 1;
int k = qpow(rt, (mod - 1) / r);
for (int i = 0; i < len; i += r) {
int w = 1;
for (int j = 0; j < mid; j++, w = mul(w, k)) {
int x = a[i + j], y = mul(w, a[i + mid + j]);
a[i + j] = add(x, y), a[i + mid + j] = sub(x, y);
}
}
}
if (type) {
reverse(a.begin() + 1, a.end());
int inv = qpow(len, mod - 2);
for (int i = 0; i < len; i++) a[i] = mul(a[i], inv);
}
}
poly polymul(poly a, poly b) {
int len = a.size() + b.size() - 1;
if (a.size() <= 40 || b.size() <= 40) {
poly c(len);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++) c[i + j] = add(c[i + j], mul(a[i], b[j]));
return c;
}
int l = 1, c = 0;
while (l < len) l <<= 1, c++;
a.resize(l), b.resize(l);
change(l, c);
ntt(a, l, 0), ntt(b, l, 0);
for (int i = 0; i < l; i++) a[i] = mul(a[i], b[i]);
ntt(a, l, 1);
a.resize(len);
return a;
}
} // namespace polynomial
using namespace polynomial;
int ca[maxn + 5];
int ans[maxn + 5];
int main() {
int n, x;
scanf("%d%d", &n, &x);
init(n << 1);
for (int i = 0; i <= n; i++) ca[i] = mul(C(2 * i, i), inv[i + 1]);
poly p(ca, ca + x), q(ca, ca + n - x + 1);
p = polymul(p, q);
for (int i = 0; i < n; i++) ans[n - i + 1] = sub(ans[n - i + 1], mul(p[i], ca[n - i - 1]));
p.resize(x);
for (int i = 0; i < x; i++) p[i] = mul(sub(C(2 * x - i - 2, x - 1), C(2 * x - i - 2, x)), ifac[i]);
for (int i = 0; i <= n - x; i++) q[i] = mul(sub(C(2 * (n - x) - i, n - x), C(2 * (n - x) - i, n - x + 1)), ifac[i]);
p = polymul(p, q);
for (int i = 0; i < n; i++) ans[i + 1] = add(ans[i + 1], mul(p[i], fac[i]));
for (int i = 1; i <= n; i++) {
ans[i] = add(ans[i], ans[i - 1]);
printf("%d\n", ans[i]);
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3660kb
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: 0ms
memory: 3672kb
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