QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#695755#9120. Huge Segment Treeicpc_zhzx034TL 0ms4028kbC++1412.2kb2024-10-31 20:43:382024-10-31 20:43:43

Judging History

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

  • [2024-10-31 20:43:43]
  • 评测
  • 测评结果：TL
  • 用时：0ms
  • 内存：4028kb
查看
  • [2024-10-31 20:43:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pr;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
// #define mid ((l+r)>>1)
#define popcnt __builtin_popcountll
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
namespace Poly {

typedef long long ll;
const int mod = 998244353, G = 3, GI = 332748118;

namespace math {
	mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
	uniform_int_distribution <int> uid(0, mod - 1);

	int I;

	struct Complex {
		int a, b;

		Complex() {}
		Complex(int a, int b): a(a), b(b) {}

		inline Complex operator*(const Complex &rhs) const {
			return Complex(((ll)a * rhs.a + (ll)b * rhs.b % mod * I) % mod, ((ll)a * rhs.b + (ll)b * rhs.a) % mod);
		}
	};

	inline Complex qpow(Complex a, int b) { Complex res(1, 0); while (b) {
		if (b & 1) { res = res * a; } a = a * a; b >>= 1; } return res; }

	inline int qpow(int a, int b) { int res = 1; while (b) {
		if (b & 1) { res = (ll)res * a % mod; } a = (ll)a * a % mod; b >>= 1; } return res; }

	inline bool check(int a) {
		return qpow(a, (mod - 1) >> 1) != mod - 1;
	}

	inline int modsqrt(int a) {
		int b = 0;
		I = 0;
		while (check(I)) {
			b = uid(rng);
			I = ((ll)b * b - a + mod) % mod;
		}
		int res = qpow(Complex(b, 1), (mod + 1) >> 1).a;
		return min(res, mod - res);
	}
}

class poly {
private:
	vector <int> data;

public:
	inline void print(string sep = " ", string end = "\n") const {
		for (int i = 0; i < (int)data.size(); ++i) {
			cout << data[i];
			if (i != (int)data.size() - 1) {
				cout << sep;
			}
		}
		cout << end;
	}

	poly(const size_t &len = size_t(0)) { data = vector <int> (len); }
	poly(const vector <int> &a) { data = a; }

	inline void clear() { data.clear(); }
	inline void resize(const size_t &len, const int &val = 0) { data.resize(len, val); }
	inline size_t size() const { return data.size(); }

	inline int &operator[](const size_t &b) { return data[b]; }
	inline const int &operator[](const size_t &b) const { return data[b]; }

	inline poly operator*(const poly &h) const;
	inline poly &operator*=(const poly &h);
	inline poly operator*(const int &h) const;
	inline poly &operator*=(const int &h);
	inline poly operator/(const int &h) const;
	inline poly &operator/=(const int &h);
	inline poly operator/(const poly &h) const;
	inline poly &operator/=(const poly &h);
	inline poly operator%(const poly &h) const;
	inline poly &operator%=(const poly &h);
	inline poly operator+(const poly &h) const;
	inline poly &operator+=(const poly &h);
	inline poly operator-(const poly &h) const;
	inline poly &operator-=(const poly &h);
	inline poly operator<<(const size_t &b) const;
	inline poly &operator<<=(const size_t &b);
	inline poly operator>>(const size_t &b) const;
	inline poly &operator>>=(const size_t &b);

	inline bool operator==(const poly &h) const;
	inline bool operator!=(const poly &h) const;

	inline poly inv() const;
	inline poly inv(const size_t &b) const;
	inline poly rev() const;
	inline poly rev(const size_t &b) const;
	inline poly Der() const;
	inline poly Der(const size_t &b) const;
	inline poly Int() const;
	inline poly Int(const size_t &b) const;
	inline poly log() const;
	inline poly log(const size_t &b) const;
	inline poly exp() const;
	inline poly exp(const size_t &b) const;
	inline poly sqrt() const;
	inline poly sqrt(const size_t &b) const;
	inline poly exsqrt() const;
	inline poly exsqrt(const size_t &b) const;
	inline poly pow(const int &h) const;
	inline poly pow(const int &h, const size_t &b) const;
};

inline void addmod(int &x) { (x >= mod) && (x -= mod); }
inline int qpow(int a, int b) { int res = 1; while (b) {
	if (b & 1) { res = (ll)res * a % mod; } a = (ll)a * a % mod; b >>= 1; } return res; }
inline int qinv(int a) { return qpow(a, mod - 2); }
inline int modsqrt(int a) { return math::modsqrt(a); }

inline void NTT(vector <int> &f, int len, int g) {
	vector <int> rev(len);
	for (int i = 0; i < len; ++i) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);
		if (rev[i] < i) {
			swap(f[i], f[rev[i]]);
		}
	}
	for (int i = 1; i < len; i <<= 1) {
		int wn = qpow(g, (mod - 1) / (i << 1));
		for (int j = 0; j < len; j += (i << 1)) {
			int w = 1;
			for (int k = 0; k < i; ++k) {
				int s = f[j + k], t = (ll)f[i + j + k] * w % mod;
				addmod(f[j + k] = s + t), addmod(f[i + j + k] = s - t + mod);
				w = (ll)w * wn % mod;
			}
		}
	}
}

inline poly poly::operator*(const poly &h) const {
	int len = 1;
	while (len < (int)(size() + h.size() - 1)) {
		len <<= 1;
	}
	vector <int> f(data), g(h.data);
	f.resize(len), g.resize(len);
	NTT(f, len, G), NTT(g, len, G);
	for (int i = 0; i < len; ++i) {
		f[i] = (ll)f[i] * g[i] % mod;
	}
	NTT(f, len, GI);
	int ilen = qinv(len);
	for (int i = 0; i < len; ++i) {
		f[i] = (ll)f[i] * ilen % mod;
	}
	f.resize(size() + h.size() - 1);
	return f;
}

inline poly &poly::operator*=(const poly &h) {
	return *this = *this * h;
}

inline poly poly::operator*(const int &h) const {
	vector <int> f(data);
	for (int i = 0; i < (int)size(); ++i) {
		f[i] = (ll)f[i] * h % mod;
	}
	return f;
}

inline poly &poly::operator*=(const int &h) {
	for (int i = 0; i < (int)size(); ++i) {
		data[i] = (ll)data[i] * h % mod;
	}
	return *this;
}

inline poly poly::operator/(const int &h) const {
	int invh = qinv(h);
	vector <int> f(data);
	for (int i = 0; i < (int)size(); ++i) {
		f[i] = (ll)f[i] * invh % mod;
	}
	return f;
}

inline poly &poly::operator/=(const int &h) {
	int invh = qinv(h);
	for (int i = 0; i < (int)size(); ++i) {
		data[i] = (ll)data[i] * invh % mod;
	}
	return *this;
}

inline poly poly::operator/(const poly &h) const {
	if (size() < h.size()) {
		return poly();
	}
	poly res = (this -> rev() * h.rev().inv(size() - h.size() + 1));
	res.resize(size() - h.size() + 1);
	return res.rev();
}

inline poly &poly::operator/=(const poly &h) {
	return *this = *this / h;
}

inline poly poly::operator%(const poly &h) const {
	poly res = *this - *this / h * h;
	res.resize(h.size() - 1);
	return res;
}

inline poly &poly::operator%=(const poly &h) {
	return *this = *this % h;
}

inline poly poly::operator+(const poly &h) const {
	vector <int> f(data);
	if (size() < h.size()) {
		f.resize(h.size());
	}
	for (int i = 0; i < (int)h.size(); ++i) {
		addmod(f[i] += h[i]);
	}
	return f;
}

inline poly &poly::operator+=(const poly &h) {
	if (size() < h.size()) {
		data.resize(h.size());
	}
	for (int i = 0; i < (int)h.size(); ++i) {
		addmod(data[i] += h[i]);
	}
	return *this;
}

inline poly poly::operator-(const poly &h) const {
	vector <int> f(data);
	if (size() < h.size()) {
		f.resize(h.size());
	}
	for (int i = 0; i < (int)h.size(); ++i) {
		addmod(f[i] += mod - h[i]);
	}
	return f;
}

inline poly &poly::operator-=(const poly &h) {
	if (size() < h.size()) {
		data.resize(h.size());
	}
	for (int i = 0; i < (int)h.size(); ++i) {
		addmod(data[i] += mod - h[i]);
	}
	return *this;
}

inline poly poly::operator<<(const size_t &b) const {
	vector <int> f(size() + b);
	for (int i = 0; i < (int)size(); ++i) {
		f[i + b] = data[i];
	}
	return f;
}

inline poly &poly::operator<<=(const size_t &b) {
	return *this = *this << b;
}

inline poly poly::operator>>(const size_t &b) const {
	if (size() <= b) {
		return poly();
	}
	vector <int> f(size() - b);
	for (int i = b; i < (int)size(); ++i) {
		f[i - b] = data[i];
	}
	return f;
}

inline poly &poly::operator>>=(const size_t &b) {
	return *this = *this >> b;
}

inline bool poly::operator==(const poly &h) const {
	if (size() != h.size()) {
		return false;
	}
	for (int i = 0; i < (int)size(); ++i) {
		if (data[i] != h[i]) {
			return false;
		}
	}
	return true;
}

inline bool poly::operator!=(const poly &h) const {
	if (size() != h.size()) {
		return true;
	}
	for (int i = 0; i < (int)size(); ++i) {
		if (data[i] != h[i]) {
			return true;
		}
	}
	return false;
}

inline poly poly::inv() const {
	vector <int> f, res(1);
	res[0] = qinv(data[0]);
	int len = 1;
	while (len < (int)size()) {
		len <<= 1;
		f.resize(len << 1), res.resize(len << 1);
		for (int i = 0; i < len; ++i) {
			if (i >= (int)size()) {
				break;
			}
			f[i] = data[i];
		}
		NTT(f, len << 1, G);
		NTT(res, len << 1, G);
		for (int i = 0; i < (len << 1); ++i) {
			int t = (ll)f[i] * res[i] % mod * res[i] % mod;
			addmod(res[i] <<= 1);
			addmod(res[i] += mod - t);
		}
		NTT(res, len << 1, GI);
		int ilen = qinv(len << 1);
		for (int i = 0; i < len; ++i) {
			res[i] = (ll)res[i] * ilen % mod;
		}
		for (int i = len; i < (len << 1); ++i) {
			res[i] = 0;
		}
	}
	res.resize(size());
	return res;
}

inline poly poly::inv(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.inv();
}

inline poly poly::rev() const {
	vector <int> f(data);
	reverse(f.begin(), f.end());
	return f;
}

inline poly poly::rev(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.rev();
}

inline poly poly::Der() const {
	vector <int> f(size());
	for (int i = 0; i < (int)size() - 1; ++i) {
		f[i] = (ll)data[i + 1] * (i + 1) % mod;
	}
	return f;
}

inline poly poly::Der(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.Der();
}

inline poly poly::Int() const {
	vector <int> f(size());
	for (int i = 1; i < (int)size(); ++i) {
		f[i] = (ll)data[i - 1] * qinv(i) % mod;
	}
	return f;
}

inline poly poly::Int(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.Int();
}

inline poly poly::log() const {
	poly res = (Der() * inv()).Int();
	res.resize(size());
	return res;
}

inline poly poly::log(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.log();
}

inline poly poly::exp() const {
	poly f, res(1);
	res[0] = 1;
	int len = 1;
	while (len < (int)size()) {
		len <<= 1;
		f.resize(len), res.resize(len);
		for (int i = 0; i < len; ++i) {
			if (i >= (int)size()) {
				break;
			}
			f[i] = data[i];
		}
		res = res - res * (res.log() - f);
		res.resize(len);
	}
	res.resize(size());
	return res;
}

inline poly poly::exp(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.exp();
}

inline poly poly::sqrt() const {
	poly f, res(1);
	res[0] = 1;
	int len = 1;
	while (len < (int)size()) {
		len <<= 1;
		f.resize(len), res.resize(len);
		for (int i = 0; i < len; ++i) {
			if (i >= (int)size()) {
				break;
			}
			f[i] = data[i];
		}
		res = (f + res * res) * (res * 2).inv();
		res.resize(len);
	}
	res.resize(size());
	return res;
}

inline poly poly::sqrt(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.sqrt();
}

inline poly poly::exsqrt() const {
	poly f, res(1);
	res[0] = modsqrt(data[0]);
	int len = 1;
	while (len < (int)size()) {
		len <<= 1;
		f.resize(len), res.resize(len);
		for (int i = 0; i < len; ++i) {
			if (i >= (int)size()) {
				break;
			}
			f[i] = data[i];
		}
		res = (f + res * res) * (res * 2).inv();
		res.resize(len);
	}
	res.resize(size());
	return res;
}

inline poly poly::exsqrt(const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.exsqrt();
}

inline poly poly::pow(const int &h) const {
	poly f(data);
	return (f.log() * h).exp();
}

inline poly poly::pow(const int &h, const size_t &b) const {
	poly f(data);
	f.resize(b);
	return f.pow(h);
}

}

using Poly::poly;
ll K;

poly a, b;

// a: whole ans
// b: non-empty prefix
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	K=read();
	a.resize(4, 0);
	a[1] = 1;
	b = a;
	for(int i=1;i<=K;i++){
		a = a * 2 + b * b;

		// a.print();
		a.resize(max(4, 2*i-1));
		(a[2] += mod-1) %= mod;
		(a[1] += 1) %= mod;
		// a.print();


		b = b + (b<<1);
		// b.print();
		(b[2] += mod-1) %= mod;
		(b[1] += 1) %= mod;
		// b.print();
		// cout<<"solved "<<i<<endl;
	}
	for(int i=1;i<=2*K-2;i++) printf("%d ",a[i]); puts("");
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3804kb

input:

2

output:

7 3

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3

output:

15 14 6 1

result:

ok 4 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

4

output:

31 43 36 19 6 1

result:

ok 6 tokens

Test #4:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

5

output:

63 110 132 114 70 30 8 1

result:

ok 8 tokens

Test #5:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

6

output:

127 255 384 448 400 272 136 47 10 1

result:

ok 10 tokens

Test #6:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

7

output:

255 558 978 1401 1610 1478 1066 589 240 68 12 1

result:

ok 12 tokens

Test #7:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

8

output:

511 1179 2292 3803 5250 5987 5576 4183 2482 1137 388 93 14 1

result:

ok 14 tokens

Test #8:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

9

output:

1023 2438 5088 9398 14896 20038 22632 21250 16406 10282 5144 2006 588 122 16 1

result:

ok 16 tokens

Test #9:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

10

output:

2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1

result:

ok 18 tokens

Test #10:

score: 0
Accepted
time: 0ms
memory: 3996kb

input:

11

output:

4095 10070 22782 48209 92140 156292 232068 298744 330926 313422 252186 171122 97008 45368 17200 5155 1176 192 20 1

result:

ok 20 tokens

Test #11:

score: -100
Time Limit Exceeded

input:

500000

output:

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-05 03:19:20 | 開源專案