小清新马蜂.抽象.神必问题 求调
查看原帖
小清新马蜂.抽象.神必问题 求调
481106
Aaron_Romeo楼主2024/8/25 09:03
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
typedef long long ll;
const ll N = 1e6;
const ll mod = 998244353;
inline ll read() {ll x; return scanf("%lld", &x), x;}
namespace poly
{
	typedef long long ll;
	const ll K = 18;
	const ll N = 1 << K;
	const ll mod = 998244353;
	const ll g = 3;
	inline ll qpow(ll a, ll b)
	{
		ll res = 1;
		while (b)
		{
			if (b & 1) res = (ll)res * a % mod;
			a = (ll)a * a % mod;
			b >>= 1;
		}
		return res;
	}
	ll invs[N + 5], log[N + 5];
	__attribute__((constructor)) inline void init()
	{
		invs[1] = 1;
		for (ll i = 2; i <= N; i ++ ) invs[i] = (ll)(mod - mod / i) * invs[mod % i] % mod;
		log[0] = -1;
		for (ll i = 1; i <= N; i ++ ) log[i] = log[i / 2] + 1;
		for (ll i = 1; i <= N; i ++ ) log[i] += 1 << log[i] < i ? 1 : 0;
	}
    inline void NTT(ll a[], ll n, ll type)
	{
		for (ll i = 0, j = 0; i < n; i ++ )
		{
			if (i < j) std :: swap(a[i], a[j]);
			for (ll k = n >> 1; (j ^= k) < k; k >>= 1) ;
		}
		static ll w[N + 5];
		w[0] = 1;
		for (ll m = 1; m < n; m <<= 1)
		{
			ll x = qpow(g, (mod - 1) / (m * 2));
			if (!~type) x = qpow(x, mod - 2);
			for (ll i = m - 2; i >= 0; i -= 2) w[i] = w[i >> 1], w[i + 1] = (ll)w[i] * x % mod;
			for (ll j = 0; j < n; j += m << 1)
				for (ll i = j; i < j + m; i ++ )
				{
					ll p = a[i], q = (ll)a[i + m] * w[i - j] % mod;
					(a[i] = p + q) >= mod && (a[i] -= mod), (a[i + m] = p - q) < 0 && (a[i + m] += mod);
				}
		}
		if (~type) return ;
		ll t = invs[n];
		for (ll i = 0; i < n; i ++ ) a[i] = (ll)a[i] * t % mod;
	}
	inline ll get_len(ll n) {return 1 << log[n];}
	inline void derit(ll a[], ll b[], ll n)
	{
		ll x[n + 5];
		for (ll i = 0; i < n; i ++ ) x[i] = (ll)a[i + 1] * (i + 1) % mod;
		for (ll i = 0; i < n; i ++ ) b[i] = x[i];
	}
	inline void intgral(ll a[], ll b[], ll n)
	{
		ll x[n + 5];
		for (ll i = 1; i <= n; i ++ ) x[i] = (ll)a[i - 1] * invs[i] % mod; x[0] = 0;
		for (ll i = 0; i <= n; i ++ ) b[i] = x[i];
	}
	inline void mul(ll a[], ll b[], ll c[], ll n, ll m, ll p)
	{
		ll k = get_len(n + m + 1);
		ll x[k + 5], y[k + 5];
		if (n <= 16 || m <= 16)
		{
			for (ll i = 0; i <= n + m; i ++ ) x[i] = 0;
			for (ll i = 0; i <= n; i ++ )
				for (ll j = 0; j <= m; j ++ )
					(x[i + j] += (ll)a[i] * b[j] % mod) >= mod && (x[i + j] -= mod);
			for (ll i = 0; i <= p; i ++ ) c[i] = x[i];
			return ;
		}
		for (ll i = 0; i < k; i ++ ) x[i] = i <= n ? a[i] : 0, y[i] = i <= m ? b[i] : 0;
		NTT(x, k, 1), NTT(y, k, 1);
		for (ll i = 0; i < k; i ++ ) x[i] = (ll)x[i] * y[i] % mod;
		NTT(x, k, -1);
		for (ll i = 0; i <= p; i ++ ) c[i] = x[i];
	}
	inline void inv(ll a[], ll b[], ll n)
	{
		ll k = get_len(n);
		ll x[2 * k + 5], y[2 * k + 5], z[k + 5];
		ll m = 1;
		z[0] = qpow(a[0], mod - 2);
		while (m < k)
		{
			m <<= 1;
			for (ll i = 0; i < 2 * m; i ++ ) x[i] = i < m && i < n ? a[i] : 0, y[i] = i < m / 2 ? z[i] : 0;
			NTT(x, 2 * m, 1), NTT(y, 2 * m, 1);
			for (ll i = 0; i < 2 * m; i ++ ) x[i] = (2 - (ll)x[i] * y[i] % mod + mod) * y[i] % mod;
			NTT(x, 2 * m, -1);
			for (ll i = 0; i < m; i ++ ) z[i] = x[i];
		}
		for (ll i = 0; i < n; i ++ ) b[i] = z[i];
	}
	inline void ln(ll a[], ll b[], ll n)
	{
		ll x[n + 5], y[n + 5];
		derit(a, x, n - 1), inv(a, y, n - 1), mul(x, y, x, n - 1, n - 1, n - 1), intgral(x, b, n - 1);
	}
	inline void exp(ll a[], ll b[], ll n)
	{
		ll k = get_len(n);
		ll x[k + 5], y[k + 5];
		ll m = 1;
		for (ll i = 0; i < k; i ++ ) y[i] = 0;
		y[0] = 1;
		while (m < k)
		{
			m <<= 1;
			ln(y, x, m);
			for (ll i = 0; i < m; i ++ ) (x[i] = (i ? 0 : 1) + (i < n ? a[i] : 0) - x[i]) < 0 && (x[i] += mod), (x[0] >= mod) && (x[0] -= mod);
			mul(x, y, x, m - 1, m - 1, m - 1);
			for (ll i = 0; i < m; i ++ ) y[i] = x[i];
		}
		for (ll i = 0; i < n; i ++ ) b[i] = y[i];
	}
}
ll a[N + 5], b[N + 5];
signed main()
{
	#ifdef LOCAL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif 
	ll n = read();
	for (ll i = 0; i < n; i ++ ) a[i] = read();
	poly :: exp(a, b, n);
	for (ll i = 0; i < n; i ++ ) printf("%lld ", b[i]);
	return 0;
}
2024/8/25 09:03
加载中...