多项式模板
\(\text{导数运算法则}\)
$ (x \pm y)' = x' \pm y' $
$ (ax)' = ax' $ (\(a\)为常数)
\((xy)' = x'y + xy'\)
$ (\displaystyle \frac{x}{y})' = \displaystyle \frac{x'y - xy'}{y^2} $
\(\text{求导公式}\)
$ (x^n)' = n x^{n - 1} $
$ (\ln x)' = \displaystyle \frac{1}{x} $
$ f(g(x))' = f'(g(x))g'(x) $
\(\text{多项式求逆}\)
递归求解，以下默认 \(f(x)\) 为题目给定多项式， \(g(x)\) 为所求多项式， \(h(x)\) 为已经求出的多项式
\[f(x)g(x) \equiv 1 \ (mod \ x^n)
\]
\]
\[f(x)g(x) \equiv 1 \ (mod \ x^{\lceil \frac{x}{2} \rceil})
\]
\]
\[f(x)h(x) \equiv 1 \ (mod \ x^{\lceil \frac{x}{2} \rceil})
\]
\]
\[h(x) - g(x) \equiv 0 \ (mod \ x^{\lceil \frac{x}{2} \rceil})
\]
\]
\[(h(x) - g(x))^2 \equiv 0 \ (mod \ x^{n})
\]
\]
\[h^2(x) + g^2(x) - 2h(x)g(x) \equiv 0 \ (mod \ x^{n})
\]
\]
两边同乘 \(f(x)\)
\[f(x)h^2(x) + g(x) - 2h(x) \equiv 0 \ (mod \ x^{n})
\]
\]
\[g(x) \equiv h(x)(2 - f(x)h(x)) \ (mod \ x^{n})
\]
\]
边界： $ g_0 = f_{0}^{-1} \ (mod \ p) $
\(\text{多项式开根}\)
递归求解
\[g^2(x) \equiv f(x) \ (mod \ x^{n})
\]
\]
\[h^2(x) \equiv f(x) \ (mod \ x^{\lceil \frac{x}{2} \rceil})
\]
\]
\[h^2(x) - f(x) \equiv 0 \ (mod \ x^{\lceil \frac{x}{2} \rceil})
\]
\]
\[(h^2(x) - f(x))^2 \equiv 0 \ (mod \ x^n)
\]
\]
\[h^4(x) + f^2(x) - 2f(x)h^2(x) \equiv 0 \ (mod \ x^n)
\]
\]
\[h^4(x) + f^2(x) + 2f(x)h^2(x) \equiv 4f(x)h^2(x) \ (mod \ x^n)
\]
\]
\[\displaystyle \frac{h^4(x) + f^2(x) + 2f(x)h^2(x)}{4h^2(x)} \equiv f(x) \ (mod \ x^n)
\]
\]
\[\left(\displaystyle \frac{h^2(x) + f(x)}{2h(x)} \right)^2 \equiv f(x) \ (mod \ x^n)
\]
\]
\[g(x) \equiv \displaystyle \frac{h^2(x) + f(x)}{2h(x)} \ (mod \ x^n)
\]
\]
\[g(x) \equiv \displaystyle \frac{h(x) + \frac{f(x)}{h(x)}}{2} \ (mod \ x^n)
\]
\]
边界： $ g_0 = \sqrt{f_0} \ (mod \ p) $ (二次剩余)
\(\text{多项式对数函数 ln}\)
\[g(x) \equiv \ln f(x) \ (mod \ x^n)
\]
\]
设 $ F(x) = \ln x $ ，原式化为
\[g(x) \equiv F(f(x)) \ (mod \ x^n)
\]
\]
两边同时求导
\[g'(x) \equiv F'(f(x))f'(x) \ (mod \ x^n)
\]
\]
\[g'(x) \equiv \displaystyle \frac{f'(x)}{f(x)} \ (mod \ x^n)
\]
\]
最后再积分回来即可
\(\text{多项式指数函数 exp}\)
使用牛顿迭代法
\[G(x) \equiv G_0(x) - \displaystyle \frac{F(G_0(x))}{F'(G_0(x))} \ (mod \ x^n)
\]
\]
证明：引入泰勒展开式
\(F(G(x))\) 在 \(G_{0}(x)\) 处泰勒展开：
\[F(G(x)) = \sum_{i = 0}^{+\infty} \displaystyle \frac{F^{(i)}(G_0(x))}{i!} (G(x) - G_0(x))^i \equiv 0 \ (mod \ x^n)
\]
\]
假设我们要求 \(G(x)\) 满足 $ F(G(x)) \equiv 0 \ (mod \ x^n) $
已知 \(G_0(x)\) 满足 $ F(G_0(x)) \equiv 0 \ (mod \ x^{\lceil \frac{x}{2} \rceil}) $
因为 $ (G(x) - G_0(x))^2 \equiv 0 \ (mod \ x^n) $
所以泰勒展开式中从第三项开始后面在 $ mod \ x^n $ 意义下都为0
即 $ F(G(x)) \equiv F(G_0(x)) + F'(G_0(x))(G(x) - G_0(x)) \equiv 0 \ (mod \ x^n) $
\[G(x) \equiv G_0(x) - \displaystyle \frac{F(G_0(x))}{F'(G_0(x))} \ (mod \ x^n)
\]
\]
\(\text{回到本题}\)
\[g(x) \equiv e^{f(x)} \ (mod \ x^n)
\]
\]
\[\ln g(x) \equiv f(x) \ (mod \ x^n)
\]
\]
设 $ F(g(x)) = \ln g(x) - f(x) $ ，应用牛顿迭代公式
\[g(x) \equiv h(x) - \displaystyle \frac{\ln h(x) - f(x)}{\frac{1}{h(x)}} \ (mod \ x^n)
\]
\]
\[g(x) \equiv h(x)(1 - \ln h(x) + f(x)) \ (mod \ x^n)
\]
\]
边界： 当 \(f_0 = 0\) 时， \(g_0 = 1\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c != EOF && c < '0') f |= (c == '-'), c = getchar();
while(c != EOF && c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const ll inv2 = (998244353 + 1) / 2;
const ll mod = 998244353;
const int N = 1 << 20 | 5;
int n, R[N];
ll inv[N], f[N], g[N], A[N], B[N], C[N], D[N], E[N], F[N];
ll qpow(ll a, ll b, ll mod)
{
ll ans = 1;
while(b)
{
if(b & 1) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
void Dev(ll *f, ll *g, int n)
{
for(int i = 1; i < n; ++i) g[i - 1] = f[i] * i % mod;
f[n - 1] = 0;
}
void InDev(ll *f, ll *g, int n)
{
for(int i = 1; i < n; ++i) g[i] = f[i - 1] * inv[i] % mod;
g[0] = 0;
}
void NTT(ll *a, int n, int type)
{
for(int i = 0; i < n; ++i) if(R[i] > i) swap(a[R[i]], a[i]);
for(int t = n >> 1, d = 1; d < n; d <<= 1, t >>= 1)
{
ll w = qpow(3, (mod - 1) / (d << 1), mod);
if(type == -1) w = qpow(w, mod - 2, mod);
for(int i = 0; i < n; i += (d << 1))
{
ll W = 1;
for(int j = 0; j < d; ++j)
{
ll tmp = W * a[i + j + d] % mod;
a[i + j + d] = (a[i + j] - tmp + mod) % mod;
a[i + j] = (a[i + j] + tmp) % mod;
W = W * w % mod;
}
}
}
if(type == -1)
{
ll inv = qpow(n, mod - 2, mod);
for(int i = 0; i < n; ++i) a[i] = a[i] * inv % mod;
}
}
void Inv(ll *f, ll *g, int n)
{
g[0] = qpow(f[0], mod - 2, mod);
ll *a = A, *b = B;
for(int d = 2, t = 4; d < (n << 1); d <<= 1, t <<= 1)
{
for(int i = 0; i < d; ++i) a[i] = f[i], b[i] = g[i];
for(int i = d; i < t; ++i) a[i] = b[i] = 0;
for(int i = 0; i < t; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) ? d : 0);
NTT(a, t, 1), NTT(b, t, 1);
for(int i = 0; i < t; ++i) g[i] = (2ll - a[i] * b[i] % mod + mod) % mod * b[i] % mod;
NTT(g, t, -1);
for(int i = d; i < t; ++i) g[i] = 0;
}
}
void Sqrt(ll *f, ll *g, int n)
{
g[0] = 1;
ll *a = C, *b = D, d, t;
for(d = 1, t = 2; d < (n << 1); d <<= 1, t <<= 1)
{
for(int i = 0; i < d; ++i) a[i] = f[i];
for(int i = d; i < t; ++i) a[i] = 0;
Inv(g, b, d);
for(int i = 0; i < t; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) ? d : 0);
NTT(a, t, 1), NTT(b, t, 1);
for(int i = 0; i < t; ++i) a[i] = a[i] * b[i] % mod;
NTT(a, t, -1);
for(int i = 0; i < d; ++i) g[i] = (g[i] + a[i]) * inv2 % mod;
for(int i = d; i < t; ++i) g[i] = 0;
}
}
void In(ll *f, ll *g, int n)
{
ll *a = C, *b = D;
Dev(f, a, n);
Inv(f, b, n);
int lim, L;
for(lim = 1, L = 0; lim < (n << 1); lim <<= 1, ++L);
for(int i = 0; i < lim; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
for(int i = n; i < lim; ++i) a[i] = b[i] = 0;
NTT(a, lim, 1), NTT(b, lim, 1);
for(int i = 0; i < lim; ++i) a[i] = a[i] * b[i] % mod;
NTT(a, lim, -1);
InDev(a, g, n);
for(int i = 0; i < lim; ++i) a[i] = b[i] = 0;
}
void Exp(ll *f, ll *g, int n)
{
g[0] = 1;
ll *a = E, *b = F;
for(int d = 2, t = 4; d < (n << 1); d <<= 1, t <<= 1)
{
In(g, b, d);
for(int i = 0; i < d; ++i) b[i] = ((i == 0) - b[i] + f[i] + mod) % mod;
for(int i = 0; i < d; ++i) a[i] = g[i];
for(int i = 0; i < t; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) ? d : 0);
NTT(a, t, 1), NTT(b, t, 1);
for(int i = 0; i < t; ++i) a[i] = a[i] * b[i] % mod;
NTT(a, t, -1);
for(int i = 0; i < d; ++i) g[i] = a[i];
}
}
int main()
{
n = read();
inv[0] = inv[1] = 1;
for(int i = 2; i < (1 << 20); ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for(int i = 0; i < n; ++i) f[i] = read();
Exp(f, g, n);
for(int i = 0; i < n; ++i) printf("%lld ", g[i]);
return 0;
}
原文链接: https://www.cnblogs.com/wenqizhi/p/17068643.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/314339
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
