QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93892#6196. Minimum Element Problemwhatever#TL 14ms20960kbC++174.6kb2023-04-03 17:46:162023-04-03 17:46:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-03 17:46:20]
  • 评测
  • 测评结果:TL
  • 用时:14ms
  • 内存:20960kb
  • [2023-04-03 17:46:16]
  • 提交

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

详细

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

output:


result: