萌新样例没过求助/kel
查看原帖
萌新样例没过求助/kel
406941
Register_int-std=c++14楼主2022/8/29 21:11

我又回来了
一个很神奇的封装。据调试输出,主要原因是 ln 函数漏了一位(过板子没问题)。有没有大佬帮忙看一下

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

namespace polynomial {
	
	vector<int> rev;
	
	int getrev(int n) {
	    int l = 1;
	    while (l < n << 1) l <<= 1;
	    rev.resize(l);
	    for (int i = 1; i < l; i++) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? l >> 1 : 0);
	    return l;
	}
	
	const int mod = 998244353;
	const int gw = 3, invgw = 332748118;
	
	ll qpow(ll b, ll p) {
	    ll res = 1;
	    while (p) {
	        if (p & 1) res = res * b % mod;
	        b = b * b % mod, p >>= 1;
	    }
	    return res;
	}
	
	ll inv(ll n) { return qpow(n, mod - 2); }
	
	template 
	<typename T> 
	class poly {
		
	private:
		vector<T> func;
		
	public:
		T &operator [] (int n) { return func[n]; }
		void resize(size_t n) { func.resize(n), rev.resize(n); }
		size_t size() const { return func.size(); }
		void push_back(T x) { func.push_back(x); }
		
		poly<T>() {}
		poly<T>(size_t n) { resize(n); }
		~poly<T>() {}
		
		void ntt(bool t) {
		    for (int i = 0; i < size(); i++) {
		        if (i < rev[i]) swap(func[i], func[rev[i]]);
		    }
		    for (int i = 1; i < size(); i <<= 1) {
		        T w = qpow(t ? invgw : gw, (mod - 1) / (i << 1));
		        for (int j = 0; j < size(); j += i << 1) {
		            T wn = 1, x;
		            for (int k = j; k < i + j; k++) {
		                x = wn * func[i + k] % mod;
		                func[i + k] = (func[k] - x + mod) % mod;
		                func[k] = (func[k] + x) % mod;
		                wn = wn * w % mod;
		            }
		        }
		    }
		    if (t) {
		        int q = qpow(size(), mod - 2);
		        for (int i = 0; i < size(); i++) func[i] = func[i] * q % mod;
		    }
		}
		
		void print() {
			for (int i = 0; i < size(); i++) printf("%lld ", func[i]); puts("");
		}
	
	public: 
		poly operator + (const poly &rhs) const {
			poly res(max(size(), rhs.size()));
			for (int i = 0; i < res.size(); i++) res[i] = (func[i] + rhs[i]) % mod;
			return res;
		}
		poly operator - (const poly &rhs) const {
			poly res(max(size(), rhs.size()));
			for (int i = 0; i < res.size(); i++) res[i] = (func[i] - rhs[i] + mod) % mod;
			return res;
		}
		poly operator * (const poly &rhs) const {
			int n = size();
			poly f = *this, g = rhs;
			int l = getrev(n); f.resize(l), g.resize(l);
			poly res(l);
			f.ntt(0), g.ntt(0);
			for (int i = 0; i < l; i++) res[i] = f[i] * g[i] % mod;
			res.ntt(1), res.resize(n);
			return res;
		}
		
		poly &operator += (const poly &rhs) { return *this = *this + rhs; }
		poly &operator -= (const poly &rhs) { return *this = *this - rhs; }
		poly &operator *= (const poly &rhs) { return *this = *this * rhs; }
	};
	
	template 
	<typename T> 
	poly<T> inv(poly<T> f) {
		static int stk[30], tot = 0, n = f.size();
		poly<T> g, a;
	    while (n > 1) stk[++tot] = n, n = n + 1 >> 1;
	    stk[tot + 1] = 1, g.push_back(inv(f[0]));
	    for (; tot; tot--) {
	    	int l = getrev(stk[tot]);
			g.resize(l), a.resize(l);
	    	for (int i = 0; i < stk[tot]; i++) a[i] = f[i];
	    	for (int i = stk[tot]; i < l; i++) a[i] = 0;
	    	for (int i = stk[tot + 1]; i < l; i++) g[i] = 0;
	    	a.ntt(0), g.ntt(0);
	    	for (int i = 0; i < l; i++) g[i] = (2 - a[i] * g[i] % mod + mod) % mod * g[i] % mod;
	    	g.ntt(1);
		}
		g.resize(stk[1]);
		return g;
	}
	
	template 
	<typename T> 
	poly<T> differential(poly<T> f) {
		poly<T> g(f.size());
	    for (int i = 1; i < f.size(); i++) g[i - 1] = i * f[i] % mod;
	    g[f.size() - 1] = 0;
	    return g;
	}
	
	template 
	<typename T> 
	poly<T> integral(poly<T> f) {
		poly<T> g(f.size());
		g[0] = 0;
		for (int i = 1; i < f.size(); i++) g[i] = f[i - 1] * qpow(i, mod - 2) % mod;
		return g;
	}
	
	template 
	<typename T> 
	poly<T> ln(poly<T> f) {
		poly<T> g = integral(differential(f) * inv(f));
		return g;
	}

	template 
	<typename T> 
	poly<T> exp(poly<T> f) {
		static int stk[30], tot = 0, n = f.size();
	    while (n > 1) stk[++tot] = n, n = n + 1 >> 1;
	    poly<T> a, g; g.push_back(1);
	    for (; tot; tot--) {
	    	a.resize(stk[tot]), g.resize(stk[tot]);
	    	a = ln(g);
		    a[0] = (f[0] + 1 - a[0] + mod) % mod;
		    for (int i = 1; i < stk[tot]; i++) a[i] = (f[i] - a[i] + mod) % mod;
		    g *= a;
		}
		return g;
	}
}

using namespace polynomial;

int n;

int main() {
	scanf("%d", &n);
	poly<ll> ans(n);
	for (int i = 0; i < n; i++) scanf("%lld", &ans[i]);
	exp(ans).print();
}
2022/8/29 21:11
加载中...