暴力 ln,Exp 和求逆的记录

· · 个人记录

暴力 ln,Exp 和求逆的记录

很短一篇博客，只是为了记录我经常忘的 两个式子 现在是三个了。

设 \ln F=G，求导即 \dfrac{F '}{F}=G'，即：

F'-FG'=0

这样的话，如果设：

F(z)=\sum_{n\ge 0}f_nz^n,G(z)=\sum_{n\ge 0}g_nz^n

这样的话，它们的系数满足：

(n+1)f_{n+1}-\sum_{i=1}^{n+1}ig_if_{n+1-i}=0

这样显然我们就得到了：

f_n=\dfrac{1}{n}\sum_{i=1}^nf_{n-i}ig_i,g_n=f_n-\dfrac{1}{n}\sum_{i=1}^{n-1}f_{n-i}ig_i

注意到第二个式子是正确的，是因为 \ln F 良定义的，当且仅当 f_0=1。这样我们就可以在 \mathcal{O}(n^2) 的时间内求解多项式 \exp,\ln 了，且对模数没有任何要求。

多项式 \exp：

#include <cstdio>
const int N = 1e5 + 10, mod = 998244353; int f[N], g[N];
inline int ksm(int a, int b)
{
    int ret = 1;
    while (b) { if (b & 1) ret = 1ll * ret * a % mod; a = 1ll * a * a % mod; b >>= 1; }
    return ret; 
}
int main()
{
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &g[i]);
    f[0] = 1; printf("%d ", f[0]);
    for (int i = 1; i < n; ++i)
    {
        for (int j = 1; j <= i; ++j) (f[i] += 1ll * f[i - j] * j % mod * g[j] % mod) %= mod;
        f[i] = 1ll * f[i] * ksm(i, mod - 2) % mod; printf("%d ", f[i]);
    }
    puts(""); return 0;
}

多项式 \ln：

#include <cstdio>
const int N = 1e5 + 10, mod = 998244353; int f[N], g[N];
inline int ksm(int a, int b)
{
    int ret = 1;
    while (b) { if (b & 1) ret = 1ll * ret * a % mod; a = 1ll * a * a % mod; b >>= 1; }
    return ret; 
}
int main()
{
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &f[i]);
    g[0] = 0; printf("%d ", g[0]);
    for (int i = 1; i < n; ++i)
    {
        for (int j = 1; j < i; ++j) (g[i] += 1ll * f[i - j] * j % mod * g[j] % mod) %= mod;
        g[i] = 1ll * g[i] * ksm(i, mod - 2) % mod; g[i] = (0ll + f[i] - g[i] + mod) % mod; 
        printf("%d ", g[i]);
    }
    puts(""); return 0;
}

求逆比上面俩简单一点。因为有 F\times G=1，继续沿用上面 F,G 的定义，我们可以得到：

\sum_{i=0}^{n}f_ig_{n-i}=[z^n](F\times G)(z)=[n=0] $$\sum_{i=0}^{n-1}f_ig_{n-i}+f_ng_0=0$$ 从而有： $$f_n=-\dfrac{1}{g_0}\sum_{i=0}^{n-1}f_ig_{n-i}$$ 这样，就可以在 $\mathcal{O}(n^2)$ 的时间求出整个 $F$ 了，对模数没有限制。 多项式求逆： ```cpp #include <cstdio> const int N = 1e5 + 10, mod = 998244353; int F[N], G[N]; inline int ksm(int a, int b) { int ret = 1; while (b) { if (b & 1) ret = 1ll * ret * a % mod; a = 1ll * a * a % mod; b >>= 1; } return ret; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", F + i); int inv = ksm(F[0], mod - 2); G[0] = inv; for (int i = 1, t; i < n; ++i) { t = 0; for (int j = 0; j < i; ++j) (t += 1ll * G[j] * F[i - j] % mod) %= mod; G[i] = 1ll * (mod - inv) * t % mod; } for (int i = 0; i < n; ++i) printf("%d ", G[i]); puts(""); return 0; } ```