QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107802#6196. Minimum Element ProblemNarratorRE 3ms3664kbC++145.5kb2023-05-22 20:56:172023-05-22 20:56:18

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-22 20:56:18]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:3664kb
  • [2023-05-22 20:56:17]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: