我又回来了
一个很神奇的封装。据调试输出,主要原因是 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();
}