知識總結 多項式全家桶(二)(ln和exp)

2022-09-22 17:53:56 字數 2659 閱讀 6204

求一個多項式\(b(x)\),滿足\(b(x)=\ln(a(x))\)。

這裡需要一些最基本的微積分知識(不會?戳我(暫時戳不動):【知識總結】微積分初步挖坑待填)。

另外,\(n\)次多項式\(a(x)\)可以看成關於\(x\)的\(n\)次函式,可以對其求導。顯然,\(a(x)=\sum\limits_^a_ix^i\)的導數是\(a'(x)=\sum\limits_^a_x^i(i+1)\),積分是\(\int a(x)\mathrm x=\sum\limits_^\frac}x^i\)。可以寫出如下**(非常簡單):

void derivative(const int *a, int *b, const int n)

void integral(const int *a, int *b, const int n)

\(f(x)=\ln(x)\)的導數是\(f'(x)=\frac\)。回到原問題,對兩邊同時求導,得到(要用一下鏈式法則\(g(f(x))\)的導數是\(g'(f(x))f'(x)\)):

\[b'(x)=a'(x)\frac=\frac

\]求個\(a(x)\)的逆元(多項式求逆)然後乘上\(a'(x)\),最後把\(b(x)\)積分回去就好了。

至於**……下面算多項式指數函式的時候要算對數函式,所以暫時省略。

求多項式\(b(x)\)滿足\(b(x)=e^\)。

首先,這個式子相當於求\(\ln b(x)=a(x)\)即\(\ln b(x)-a(x)=0\)

設關於多項式的函式\(f(b(x))=\ln b(x)-a(x)\),那麼問題就是求這個函式的零點(\(a(x)\)是給定的,視作常數)。

求函式零點的方法之一是牛頓迭代,公式如下(\(i\)是迭代次數,\(x\)是自變數,\(f(x)\)是要求零點的函式,\(f'(x_0)\)是\(f(x)\)在\(x_0\)處的導數):

\[x_=x_i-\frac

\]把\(f(b(x))=\ln b(x)-a(x)\)求導,得到\(f'(b(x))=\frac\)(注意自變數是\(b(x)\)不是\(x\)。這不是一個\(f(x)\)和\(b(x)\)的複合函式)。然後代入上面的公式:

\[\begin

b_(x)&=b_i(x)-\frac}\\

&=b_i(x)-b_i(\ln b_i(x)-a(x))\\

&=b_i(x)(1-\ln b_i(x)-a(x))

\end

\]由於多項式乘法的存在,每迭代一次\(b\)的有效長度會增加一倍。

**(洛谷4726):

#include #include #include #include #undef i

#undef j

#undef k

#undef true

#undef false

#undef min

#undef max

#undef swap

#undef sort

#undef if

#undef for

#undef while

#undef printf

#undef scanf

#undef putchar

#undef getchar

#define _ 0

using namespace std;

namespace zyt

templateinline void write(t x)

typedef long long ll;

const int n = 1e5 + 10, len = (n << 2), p = 998244353, g = 3;

namespace polynomial

return ans;

} inline int inv(const int a)

int omega[len], winv[len], rev[len];

void init(const int n, const int lg2)

for (int i = 0; i < n; i++)

rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (lg2 - 1)));

} void ntt(int *a, const int *w, const int n)

}void mul(const int *a, const int *b, int *c, const int n)

void _inv(const int *a, int *b, const int n)

}void inv(const int *a, int *b, const int n)

void derivative(const int *a, int *b, const int n)

void integral(const int *a, int *b, const int n)

void ln(const int *a, int *b, const int n)

void _exp(const int *a, int *b, const int n)

}void exp(const int *a, int *b, const int n)

}int work() }

int main()