这是本人的代码,高度封装,已经通过了本题,但还有一个小问题不理解:
struct poly_t
{
int a[MaxA];
poly_t() { memset(a, 0, sizeof(a)); }
inline auto &operator[](int x) { return a[x]; }
inline auto &operator[](int x) const { return a[x]; }
poly_t &operator*=(const poly_t &f)
{
for (int i = 0; i < lim; i++) a[i] = 1l * a[i] * f[i] % mod;
return *this;
}
poly_t &Diff(const poly_t &f, int n)
{
for (int i = 1; i < n; i++) a[i - 1] = 1l * i * f[i] % mod;
a[n - 1] = 0; return *this;
}
poly_t &Int(const poly_t &f, int n)
{
for (int i = n - 1; i; i--) a[i] = 1l * inv[i] * f[i - 1] % mod;
a[0] = 0; return *this;
}
poly_t &NTT(int t)
{
for (int i = 0; i < lim; i++)
if (i < r[i]) std::swap(a[i], a[r[i]]);
for (int h = 1; h < lim; h <<= 1)
for (int i = 0; i < lim; i += h << 1)
for (int j = 0, s = 1; j < h; j++, s = 1l * s * w[t][h] % mod)
{
int u = a[i | j], v = 1l * s * a[i | h | j] % mod;
a[i | j] = (u + v) % mod, a[i | h | j] = (u - v + mod) % mod;
}
if (t) for (int i = 0, inv = qpow(lim, mod - 2); i < lim; i++)
a[i] = 1l * a[i] * inv % mod;
return *this;
}
poly_t &Inv(const poly_t &f, int n)
{
poly_t g; a[0] = qpow(f[0], mod - 2);
for (int m = 2; m < n << 1; m <<= 1)
{
memcpy(g.a, f.a, m << 2);
init_NTT(m << 1), NTT(0), g.NTT(0);
for (int i = 0; i < lim; i++)
a[i] = (mod - 1l * g[i] * a[i] % mod + 2) * a[i] % mod;
NTT(1);
memset(a + m, 0, m << 2); // 此处缩限了范围
}
return *this;
}
poly_t &ln(const poly_t &f, int n)
{
poly_t g, h; init_NTT(n << 1);
return Int((g.Diff(f, n).NTT(0) *= h.Inv(f, n).NTT(0)).NTT(1), n);
}
poly_t &exp(const poly_t &f, int n)
{
poly_t g; a[0] = 1;
for (int m = 2; m < n << 1; m <<= 1)
{
g.ln(*this, m)[0]--;
for (int i = 0; i < m; i++) g[i] = (f[i] - g[i] + mod) % mod;
init_NTT(m << 1), (NTT(0) *= g.NTT(0)).NTT(1); // ? 此处是否需要缩限范围?
}
return *this;
}
} f, g;
类比 Inv(),使用迭代法求解多项式 exp 是否需要做范围的缩限?(在一次迭代中,超出了 xm 的答案是否是错误的?)
实测不加缩限也可以通过模板,但担心有奇奇怪怪的问题,故求教广大谷民。