序

學多項式也有好久了，可是我自己還沒怎么認認真真推過柿子，導致啥都不會，然后被吊打。

看來再不回顧一下就不行了啊。

多項式乘法

寫了一個好看一點的\(\mathrm{NTT}\)板子，僅供參考。

inline int Add(int x, int y) { return (x + y) % Mod; } inline int Sub(int x, int y) { return (x - y + Mod) % Mod; } inline int Mul(int x, int y) { return 1ll * x * y % Mod; } int fastpow(int x, int y) {int ans = 1;for (; y; y >>= 1, x = 1ll * x * x % Mod)if (y & 1) ans = 1ll * ans * x % Mod;return ans; }int r[maxn], w[maxn]; void FFT(int *p, int N) {for (int i = 0; i < N; i++) if (i < r[i]) std::swap(p[i], p[r[i]]);for (int i = 1, s = 2, t = N >> 1; i < N; i <<= 1, s <<= 1, t >>= 1)for (int j = 0; j < N; j += s) for (int k = 0, o = 0; k < i; ++k, o += t){int x = p[j + k], y = 1ll * w[o] * p[i + j + k] % Mod;p[j + k] = (x + y) % Mod, p[i + j + k] = (x - y + Mod) % Mod;} }template<typename C> void PolyMul(int *a, int *b, int N, int P, C cal) {w[0] = 1, w[1] = fastpow(3, (Mod - 1) / N);for (int i = 0; i < N; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << P);for (int i = 2; i < N; i++) w[i] = 1ll * w[i - 1] * w[1] % Mod;FFT(a, N), FFT(b, N); for (int i = 0; i < N; i++) b[i] = cal(a[i], b[i]);FFT(b, N); std::reverse(b + 1, b + N); int invn = fastpow(N, Mod - 2);for (int i = 0; i < N; i++) b[i] = 1ll * b[i] * invn % Mod; }

泰勒展開

如果\(f(x)\)在\(x_0\)處存在\(n\)階導，那么有：
\[ f(x) = \sum_{i=0}^n \frac {f^{(i)}(x_0)} {i!} (x - x_0) ^ i + \xi \]
其中\(\xi\)是余項，當\(n\)趨近于無窮大時，\(\xi\)趨近于高階無窮小。

比如說\(e ^ x = 1 + \frac x{1!} + \frac {x^2}{2!} + \cdots\)

牛頓迭代

首先可以知道多項式的任何一個運算都可以表示成對于一個多項式\(B(x)\)以及一個給定的函數\(F(x)\)，求\(F(B(x)) \equiv 0 \pmod {x ^ n}\)

設\(B_n(x)\)表示當模數是\(x ^ n\)的合法解。那么當\(n = 1\)是我們很容易可以得到結果，考慮如何用\(B_n(x)\)推到\(B_{2n}(x)\)。

對\(F(B_{2n}(x))\)在\(B_n(x)\)處泰勒展開，我們得到\(F(B_{2n}(x)) = F(B_n(x)) + F'(B_n(x))(B_{2n}(x) - B_n(x))\)。

那么我們化簡一下就是：
\[ B_{2n}(x) = B_n(x) - \frac {F(B_n(x))} {F'(B_n(x))} \]
這樣我們就可以倍增求解。

多項式運算

接下來均假設我們要做運算的多項式是\(A(x)\)。

多項式求逆

令\(F(B_n(x)) = A(x) * B_n(x) - 1 \equiv 0\)

于是：
\[ \begin{aligned} B_{2n} &= B_n(x) - \frac {A(x) * B_n(x) - 1} {A(x)} \\ &= B_n(x) - B_n(x)(A(x) * B_n(x) - 1) \\ &= 2B_n(x) - A(x) * B_n^2(x) \end{aligned} \]
注意第一步推到第二步是因為\(B_n(x)\)是\(A(x)\)的逆。

void Inv(int *a, int *b, int N) {static int c[maxn]; if (N == 1) return (void) (*b = fastpow(*a, Mod - 2));Inv(a, b, (N + 1) >> 1); int L = 1, P = -1; while (L < (N << 1)) L <<= 1, ++P;std::copy(a, a + N, c), std::fill(c + N, c + L, 0);PolyMul(c, b, L, P, [] (int a, int b) { return Mul(Sub(2, Mul(a, b)), b); });std::fill(b + N, b + L, 0); }

多項式開根

ln一下再exp一下

令\(F(B_n(x)) = B_n^2(x) - A(x) \equiv 0\)

于是有：
\[ B_{2n} = B_n(x) - \frac {B_n^2(x) - A(x)} {2B_n(x)} = \frac 12\left(B_n(x) + \frac {A(x)} {B_n(x)} \right) \]
可以看出多項式開根中需要套用多項式求逆。

void Sqrt(int *a, int *b, int N) {static int c[maxn], d[maxn]; if (N == 1) return (void) (*b = 1);Sqrt(a, b, (N + 1) >> 1); int L = 1, P = -1; while (L < (N << 1)) L <<= 1, ++P;std::copy(a, a + N, c), std::fill(c + N, c + L, 0);std::fill(d, d + L, 0), Inv(b, d, N), PolyMul(c, d, L, P, Mul);for (int i = 0; i < N; i++) b[i] = Mul(Add(b[i], d[i]), 499122177); }

多項式\(\ln\)

不需要牛頓迭代。
\[ \begin{aligned} \ln(A(x)) &= B(x) \\ \Rightarrow\frac {A'(x)}{A(x)} &= B'(x) \end{aligned} \]
然后\(A(x)\)就求導求逆，乘起來再積分一下就可以了。

void Ln(int *f, int *g, int N) {static int A[maxn], B[maxn]; Inv(f, B, N), A[N - 1] = 0;for (int i = 1; i < N; i++) A[i - 1] = Mul(f[i], i);int L = 1, P = -1; while (L < (N << 1)) L <<= 1, ++P;PolyMul(A, B, L, P, Mul), g[0] = 0;for (int i = 1; i < N; i++) g[i] = Mul(B[i - 1], fastpow(i, Mod - 2));std::fill(A, A + L, 0), std::fill(B, B + L, 0); }

多項式\(\exp\)

令\(F(B_n(x)) = \ln(B_n(x)) - A(x) \equiv 0\)

推下式子可得：
\[ \begin{aligned} B_{2n}(x) &= B_n(x) - \frac {\ln(B_n(x)) - A(x)} {\frac 1 {B_n(x)}} \\ &= B_n(x)(1 - \ln(B_n(x)) + A(x)) \end{aligned} \]

void Exp(int *a, int *b, int N) {static int c[maxn]; if (N == 1) return (void) (*b = 1);Exp(a, b, (N + 1) >> 1), Ln(b, c, N);int L = 1, P = -1; while (L < (N << 1)) L <<= 1, ++P;for (int i = 0; i < N; i++) c[i] = Sub(a[i], c[i]); c[0] = Add(c[0], 1);PolyMul(c, b, L, P, Mul), std::fill(b + N, b + L, 0); }

多項式除法

給定一個\(n\)次多項式\(A(x)\)和一個\(m\)次多項式\(B(x)\)，求解一個\(n - m\)次的多項式\(Q(x)\)以及一個小于\(n - m\)次的多項式\(R(x)\)，使得\(A(x) = Q(x)B(x) + R(x)\)

定義運算\(R\)使得\(A^R(x) = x ^ nA(\frac 1x)\)，也就是說將\(A(x)\)的系數翻轉。

那么可以得到：
\[ \begin{aligned} A(x) &= Q(x)B(x) + R(x) \\ A\left(\frac 1x\right) &= Q\left(\frac 1x\right)B\left(\frac 1x\right) + R\left(\frac 1x\right) \\ x ^ nA\left(\frac 1x\right) &= \left(x ^ m B\left(\frac 1x\right)\right) * \left( x ^ {n - m} Q\left(\frac 1x\right)\right) + x ^ n R\left(\frac 1x\right) \\ A^R(x) &= Q^R(x)B^R(x) + x^{n-m+1}R^R(x) \\ A^R(x) &\equiv Q^R(x)B^R(x) \pmod{x ^ {n - m + 1}} \\ Q^R(x) &\equiv \frac {A^R(x)} {B^R(x)} \pmod{x ^ {n - m + 1}} \end{aligned} \]
那么這樣就可以用多項式求逆求出\(Q\)，再用\(R(x) = A(x) - Q(x)B(x)\)即可求出\(R\)。

轉載于:https://www.cnblogs.com/cj-xxz/p/11166903.html

總結

以上是生活随笔為你收集整理的「学习笔记」多项式相关的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。