多項式對數函數$\ln f(x)$

如果存在解必然有$[x^0]f(x)=1$，

對$\ln f(x)$求導，有$\frac{d\ln f(x)}{dx}\equiv \frac{f^{\prime }(x)}{f(x)}(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n)$，

$dx$乘到右邊，再求積分有：
$$\begin{gathered} \int d\ln f(x)\equiv \int \frac{f^{\prime }(x))}{f(x)}dx(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n) \\ \ln f(x)\equiv \int \frac{f^{\prime }(x)}{f(x)}(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n) \end{gathered}$$
然后只要對先對$f(x)$求個導，求個逆，最后求一次積分即可，整體復雜度$O(n\log n)$。

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 5e6 + 10, mod = 998244353, inv2 = mod + 1 >> 1;int a[N], b[N], c[N], d[N], r[N], inv[N];int quick_pow(int a, int n) {int ans = 1;while (n) {if (n & 1) {ans = 1ll * ans * a % mod;}a = 1ll * a * a % mod;n >>= 1;}return ans; }void get_r(int lim) {for (int i = 0; i < lim; i++) {r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);} }void get_inv(int n) {inv[1] = 1;for (int i = 2; i < n; i++) {inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;} }void NTT(int *f, int lim, int rev) {for (int i = 0; i < lim; i++) {if (i < r[i]) {swap(f[i], f[r[i]]);}}for (int mid = 1; mid < lim; mid <<= 1) {int wn = quick_pow(3, (mod - 1) / (mid << 1));for (int len = mid << 1, cur = 0; cur < lim; cur += len) {int w = 1;for (int k = 0; k < mid; k++, w = 1ll * w * wn % mod) {int x = f[cur + k], y = 1ll * w * f[cur + mid + k] % mod;f[cur + k] = (x + y) % mod, f[cur + mid + k] = (x - y + mod) % mod;}}}if (rev == -1) {int inv = quick_pow(lim, mod - 2);reverse(f + 1, f + lim);for (int i = 0; i < lim; i++) {f[i] = 1ll * f[i] * inv % mod;}} }void polyinv(int *a, int *b, int n) {if (n == 1) {b[0] = quick_pow(a[0], mod - 2);return ;}polyinv(a, b, n + 1 >> 1);int lim = 1;while (lim < 2 * n) {lim <<= 1;}get_r(lim);for (int i = 0; i < n; i++) {c[i] = a[i];}for (int i = n; i < lim; i++) {c[i] = 0;}NTT(b, lim, 1);NTT(c, lim, 1);for (int i = 0; i < lim; i++) {int cur = (2 - 1ll * c[i] * b[i] % mod + mod) % mod;b[i] = 1ll * b[i] * cur % mod;}NTT(b, lim, -1);for (int i = n; i < lim; i++) {b[i] = 0;} }void derivative(int *a, int *b, int n) {for (int i = 0; i < n; i++) {b[i] = 1ll * a[i + 1] * (i + 1) % mod;} }void integrate(int *a, int n) {get_inv(n);for (int i = n - 1; i >= 1; i--) {a[i] = 1ll * a[i - 1] * inv[i] % mod;}a[0] = 0; }void polyln(int *a, int *b, int n) {derivative(a, b, n);polyinv(a, d, n);int lim = 1;while (lim < 2 * n) {lim <<= 1;}get_r(lim);NTT(b, lim, 1);NTT(d, lim, 1);for (int i = 0; i < lim; i++) {b[i] = 1ll * b[i] * d[i] % mod;}NTT(b, lim, -1);integrate(b, n); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}polyln(a, b, n);for (int i = 0; i < n; i++) {printf("%d%c", b[i], i + 1 == n ? '\n' : ' ');}return 0; }

總結

以上是生活随笔為你收集整理的多项式对数函数ln f(x)的全部內容，希望文章能夠幫你解決所遇到的問題。

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