QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107555#6196. Minimum Element ProblemFISHER_RE 3ms3672kbC++143.1kb2023-05-21 22:59:202023-05-21 22:59:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-21 22:59:22]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:3672kb
  • [2023-05-21 22:59:20]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: