萌新求问!!!
  • 板块灌水区
  • 楼主chenyilei
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/9/27 21:09
  • 上次更新2023/11/5 12:30:20
查看原帖
萌新求问!!!
21001
chenyilei楼主2020/9/27 21:09

为什么我的exp错了 大佬们帮我看看,我交了多项式ln的模板过了,exp样例错了。帮帮忙吧

#include <bits/stdc++.h>
using namespace std;
namespace cxcyl {
	const int mod = 998244353;
	int a[400005], b[400005], rev[400005], n, m, cnt[100005], inv[400005], L;
	inline int read() {
		int x = 0, f = 1; char c = getchar();
		while (c > -1 && c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		if (c == -1) return 0;
		while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
		return x * f;
	}
	inline int fpow(int a, int b) {
		int ret = 1;
		for (; b; b >>= 1, a = 1ll * a * a % mod)
			if (b & 1)
				ret = 1ll * ret * a % mod;
		return ret;
	}
	inline void Get(int n, int op = 1) {
		L = op ? 1 : n;
		while (L < n) L <<= 1;
		for (int i = 1; i < L; ++i) rev[i] = rev[i >> 1] >> 1 | ((i & 1) ? L >> 1 : 0);
	}
	inline void fft(int *a, int t) {
		for (int i = 0; i < L; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);
		for (int l = 2; l <= L; l <<= 1) {
			int W = t == 1 ? fpow(3, (mod - 1) / l) : fpow(fpow(3, (mod - 1) / l), mod - 2);
			for (int i = 0; i < L; i += l)
				for (int j = 0, w = 1; j < l >> 1; ++j, w = 1ll * w * W % mod) {
					int x = a[i + j], y = 1ll * a[i + l / 2 + j] * w % mod;
					a[i + j] = (x + y) % mod, a[i + l / 2 + j] = (x - y) % mod;
				}
		}
		if (t == -1) for (int i = 0, v = fpow(L, mod - 2); i < L; ++i) a[i] = 1ll * a[i] * v % mod;
	}
	inline void Qiud(int *f, int *g, int n) {
		f[n - 1] = 0;
		for (int i = 1; i < n; ++i) f[i - 1] = 1ll * g[i] * i % mod;
	}
	inline void Jif(int *f, int *g, int n) {
		f[0] = 0;
		for (int i = 0; i < n - 1; ++i) f[i + 1] = 1ll * g[i] * inv[i + 1] % mod;
	}
	inline void Inv(int *f, int *g, int n) {
		int c[400005];
		f[0] = fpow(g[0], mod - 2);
		for (int l = 2; l < n << 1; l <<= 1) {
			Get(l << 1, 0);
			for (int i = 0; i < l; ++i) c[i] = g[i];
			for (int i = l; i < L; ++i) c[i] = 0;
			fft(c, 1), fft(f, 1);
			for (int i = 0; i < L; ++i) f[i] = (2 - 1ll * f[i] * c[i]) % mod * f[i] % mod;
			fft(f, -1);
			for (int i = l; i < L; ++i) f[i] = 0;
		}
		for (int i = n; i < n << 1; ++i) f[i] = 0;
	}
	inline void Ln(int *f, int *g, int n) {
		int c[400005], d[400005];
		Get(n);
		Inv(c, g, n), Qiud(d, g, n);
		for (int i = n; i < L; ++i) c[i] = d[i] = 0;
		fft(c, 1), fft(d, 1);
		for (int i = 0; i < L; ++i) d[i] = 1ll * c[i] * d[i] % mod;
		fft(d, -1);
		Jif(f, d, n);
	}
	inline void Exp(int *f, int *g, int n) {
		int c[400005];
		f[0] = 1;
		for (int l = 2; l < n << 1; l <<= 1) {
			Ln(c, f, l);
			Get(l << 1, 0);
			for (int i = 0; i < l; ++i) c[i] = (c[i] - g[i]) % mod;
			for (int i = l; i < L; ++i) c[i] = 0;
			fft(c, 1), fft(f, 1);
			for (int i = 0; i < L; ++i) f[i] = f[i] * (1ll - c[i]) % mod;
			fft(f, -1);
			for (int i = l; i < L; ++i) f[i] = 0;
		}
		for (int i = n; i < n << 1; ++i) f[i] = 0;
	}/*
	inline int main() {
		n = read(), m = read();
		for (int i = 1; i <= n; ++i) ++cnt[read()];
		for (int i = 1; i <= m; ++i)
			if (cnt[i])
				for (int j = i; j <= m; j += i)
					a[j] = (1ll * cnt[i] * inv[j / i] + a[j]) % mod;
		Exp(b, a, m + 1);
		for (int i = 1; i <= m; ++i) printf("%d\n", (b[i] + mod) % mod);
		return 0;
	}*/
	inline int main() {
		inv[1] = 1;
		for (int i = 2; i <= 400000; ++i) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
		n = read();
		for (int i = 0; i < n; ++i) a[i] = read();
		Exp(b, a, n);
		for (int i = 0; i < n; ++i) printf("%d ", (b[i] + mod) % mod);
		return 0;
	}
} int main() { return cxcyl::main(); }
2020/9/27 21:09
加载中...