25pts求助
查看原帖
25pts求助
716260
SegmentTree_楼主2024/7/25 15:18
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define lid (id << 1)
#define rid (id << 1 | 1)
//#define int long long
namespace io {
	#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
//    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	#define gc() getchar() 
    inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
    inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
    template <class I> inline void read(I &x){ for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f; }
    template <class I> inline void write(I x) { if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x; while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) putc (qu[qr --]); }
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io::read;
using io::write;
using io::putc;
namespace tianyu_poly{
	const int N = 1e6+5;
	const ll P = 998244353, G = 3, Gi = 332748118;
	const double pie = acos(-1.0);
	struct Complex{
		double x, y;
		Complex(double xx = 0, double yy = 0){ x = xx, y = yy; }
		Complex operator +(Complex a){ return Complex(x + a.x, y + a.y); }
		Complex operator -(Complex a){ return Complex(x - a.x, y - a.y); }
		Complex operator *(Complex a){ return Complex(x * a.x - y * a.y, x * a.y + y * a.x); }
		Complex operator /(Complex a){ return Complex((x * a.x + y * a.y) / (a.x * a.x + a.y * a.y), (y * a.x - x * a.y) / (a.x * a.x + a.y * a.y)); }
	};
	const Complex I = Complex(1, 0);
	Complex FFT_f[N];
	int rev[N], revmx = 0;
	ll qpow(ll a, ll b){
		ll res = 1;
		while (b){
			if (b & 1) res = res * a % P;
			a = a * a % P;
			b >>= 1;
		}
		return res;
	}
	struct Poly{
		int cs;
		int xs[N];
		Poly(int c = 0){
			cs = c;
		} 
		int & operator [](int x){
			return xs[x];
		}
		void print(){
			for (int i = 0;i <= cs;i++){
				cout << xs[i] << ' ';
			}
			cout << '\n';
		}
		Poly operator +(Poly a){
			Poly c;
			c.cs = max(a.cs, cs);
			for (int i = 0;i <= c.cs;i++){
				c.xs[i] = xs[i] + a[i];
			}
			return c;
		}
		Poly operator -(Poly a){
			Poly c;
			c.cs = max(a.cs, cs);
			for (int i = 0;i <= cs;i++){
				c.xs[i] = xs[i] + a[i];
			}
			return c;
		}
	};
	void FFT(int limit, Complex *a, int op = 1){
		for (int i = 0;i < limit;++i){
			if (rev[i] > i) swap(a[i], a[rev[i]]);
		}
		for (int mid = 1;mid < limit;mid <<= 1){
			Complex wn = Complex(cos(pie / mid), op * sin(pie / mid));
			for (int r = mid << 1, j = 0;j < limit;j += r){
				Complex	w(1, 0);
				for (int k = 0;k < mid;++k, w = w * wn){
					Complex x = a[j + k], y = w * a[j + mid + k];
					a[j + k] = x + y;
					a[j + mid + k] = x - y;
				}
			}
		}
	}	
	void NTT(int limit, int *a, int op){
		for (int i = 0;i < limit;i++){
			if (rev[i] > i) swap(a[i], a[rev[i]]);
		}
		for (int mid = 1;mid < limit;mid <<= 1){
			int wn = qpow(op == 1 ? G : Gi, (P - 1) / (mid << 1));
			for (int r = mid << 1, j = 0;j < limit;j += r){
				ll w = 1;
				for (int k = 0;k < mid;k++, w = w * wn % P){
					int x = a[j + k], y = w * a[j + mid + k] % P;
					a[j + k] = (x + y) % P;
					a[j + mid + k] = (x - y + P) % P;
				}
			}
		}
	}		
	Poly FFT_mul(Poly a, Poly b){
		Poly c;
		c.cs = a.cs + b.cs;
		for (int i = 0;i <= a.cs;i++) FFT_f[i].x = a[i];
		for (int i = 0;i <= b.cs;i++) FFT_f[i].y = b[i];
		int limit = 1, l = 0;
		while (limit <= a.cs + b.cs) limit <<= 1, ++l;
		for (int i = 0;i < limit;i++){
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
		}
		FFT(limit, FFT_f);
		for (int i = 0;i <= limit;i++) FFT_f[i] = FFT_f[i] * FFT_f[i];
		FFT(limit, FFT_f, -1);
		for (int i = 0;i <= c.cs;i++){
			c[i] = (int)(FFT_f[i].y / limit / 2.0 + 0.5);
		}
		return c;
	} 		
	Poly NTT_mul(Poly a, Poly b){
		Poly c;
		c.cs = a.cs + b.cs;
		int limit = 1, l = 0;
		while (limit <= a.cs + b.cs) limit <<= 1, ++l;
		for (int i = 0;i < limit;++i){
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
		}
		NTT(limit, a.xs, 1);
		NTT(limit, b.xs, 1);
		for (int i = 0;i <= limit;i++) a[i] = 1ll * b[i] * a[i] % P;
		NTT(limit, a.xs, -1);
		ll inv = qpow(limit, P - 2);
		for (int i = 0;i <= c.cs;i++){
			c[i] = a[i] * inv % P;
		}
		return c;
	} 
	int cdq_a[N], cdq_b[N];
	void cdq_NTT(Poly &f, Poly g, int l, int r){
		if (l == r) return;
		if (l == r - 1){
			if (!l) f[0] = 1;
			f[r] = f[r] + 1ll * f[l] * g[1] % P;
			f[r] = f[r] >= P ? f[r] - P : f[r];
			return;
		}
		int mid = (l + r) >> 1;
		cdq_NTT(f, g, l, mid);
		int limit = 1, l1 = 0;
		while (limit <= r - l + 1) limit <<= 1, ++l1;
		for (int i = 0;i < limit;++i){
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l1 - 1));
		}
		memcpy(cdq_a, f.xs + l, sizeof(int) * (mid - l + 1));
		memcpy(cdq_b, g.xs, sizeof(int) * (r - l + 1));
		memset(cdq_a + mid - l + 1, 0, sizeof(int) * (limit - mid + l));
		memset(cdq_b + r - l + 1, 0, sizeof(int) * (limit - r + l));
		NTT(limit, cdq_a, 1);
		NTT(limit, cdq_b, 1);
		for (int i = 0;i <= limit;i++) cdq_a[i] = 1ll * cdq_a[i] * cdq_b[i] % P;
		NTT(limit, cdq_a, -1);
		for (int i = mid + 1;i <= r;++i){
			ll ff = (f[i] + (cdq_a[i - l] * qpow(limit, P - 2) % P));
			f[i] = ff >= P ? ff - P : ff;
		}
		cdq_NTT(f, g, mid + 1, r);
	}
	Poly getinv(Poly a){
		Poly b[2];
		b[0][0] = qpow(a[0], P - 2) % P;
		int n = a.cs + 1;
		int bas = 1;
		b[0].cs = b[1].cs = a.cs;
		while (bas <= (n << 1)){
			for (int i = 0;i < bas;i++){
				b[1][i] = (b[0][i]) % P;
			}
			b[1] = NTT_mul(a, NTT_mul(b[1], b[1]));
			for (int i = 0;i < bas;i++){
				b[0][i] = (2ll * b[0][i] - b[1][i] + P) % P;
			}
			bas <<= 1;
		}
		return b[0];
	}
}
using tianyu_poly::Poly;
using tianyu_poly::FFT_mul;
using tianyu_poly::NTT_mul;
using tianyu_poly::cdq_NTT;
using tianyu_poly::getinv; 
namespace tianyu{
	void awa(){
		int n;
		cin >> n;
		--n;
		Poly a(n);
		for (int i = 0;i <= n;i++) cin >> a[i];
		Poly b;
		b = getinv(a);
		b.print();
	}
}
signed main(){ 
	fastio;
	int T = 1;
	while (T--){
		tianyu::awa();
	}
	return 0;
}
2024/7/25 15:18
加载中...