关于是否需要清空无用的精度部分
查看原帖
关于是否需要清空无用的精度部分
554746
yiming564楼主2024/11/4 23:43

这是本人的代码,高度封装,已经通过了本题,但还有一个小问题不理解:

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\exp 是否需要做范围的缩限?(在一次迭代中,超出了 xmx ^ m 的答案是否是错误的?)

实测不加缩限也可以通过模板,但担心有奇奇怪怪的问题,故求教广大谷民。

2024/11/4 23:43
加载中...