[Luogu P4725] 【模板】多项式对数函数

洛谷传送门

题目描述

给出 $n-1$ 次多项式 $A(x)$，求一个 $\mathrm{m}\mathrm{o}\mathrm{d}{x}^n$ 下的多项式 $B(x)$，满足 $B(x)\equiv \ln A(x)$.

在 $\text{mod }998244353$ 下进行，且 $a_i\in [0,998244353]\cap \mathbb{Z}$

输入输出格式

输入格式：

第一行一个整数 $n$.

下一行有 $n$ 个整数，依次表示多项式的系数 $a_0,a_1,\cdots ,a_{n-1}$.

保证 $a_0=1$.

输出格式：

输出 $n$ 个整数，表示答案多项式中的系数 $a_0,a_1,\cdots ,a_{n-1}$.

输入输出样例

输入样例#1：

6
1 927384623 878326372 3882 273455637 998233543

输出样例#1：

0 927384623 817976920 427326948 149643566 610586717

说明

对于 $100\%$ 的数据，$n\le 10^5$.

解题分析

两边求导可得：
$$B^{\prime }(x)\equiv \frac{A^{\prime }(x)}{A(x)}(mod{x}^n)$$
求逆， 求导最后积分回来就好了。

代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstdlib>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 400500
#define MOD 998244353
#define G 3
#define Ginv 332748118
template <class T>
IN void in(T &x)
{
x = 0; R char c = gc;
for (; !isdigit(c); c = gc);
for (;
isdigit(c); c = gc)
x = (x << 1) + (x << 3) + c - 48;
}
IN int fpow(R int base, R int tim)
{
int ret = 1;
W (tim)
{
if (tim & 1) ret = 1ll * ret * base % MOD;
base = 1ll * base * base % MOD, tim >>= 1;
}
return ret;
}
int n;
int rev[MX], a[MX], b[MX], A[MX], B[MX], Ainv[MX], Adr[MX], Bdr[MX];
namespace Poly
{
IN void NTT(int *dat, R int len, R bool typ)
{
for (R int i = 1; i < len; ++i) if (rev[i] > i) std::swap(dat[rev[i]], dat[i]);
R int seg, step, bd, now, cur, base, deal, buf1, buf2;
for (seg = 1; seg < len; seg <<= 1)
{
base = fpow(typ ? G : Ginv, (MOD - 1) / (seg << 1)), step = seg << 1;
for (now = 0; now < len; now += step)
{
deal = 1, bd = now + seg;
for (cur = now; cur < bd; cur++, deal = 1ll * deal * base % MOD)
{
buf1 = dat[cur], buf2 = 1ll * dat[cur + seg] * deal % MOD;
dat[cur] = (buf1 + buf2) % MOD, dat[cur + seg] = (buf1 - buf2 + MOD) % MOD;
}
}
}
if (typ) return; int inv = fpow(len, MOD - 2);
for (R int i = 0; i < len; ++i) dat[i] = 1ll * dat[i] * inv % MOD;
}
void Getinv(R int up, R int lg)
{
if (up == 1) return Ainv[0] = fpow(A[0], MOD - 2), void();
Getinv(up >> 1, lg - 1); R int len = up << 1;
for (R int i = 1; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg - 1);
for (R int i = up; i < len; ++i) a[i] = b[i] = 0;
for (R int i = 0; i < up; ++i) a[i] = Ainv[i], b[i] = A[i];
NTT(a, len, 1), NTT(b, len, 1);
for (R int i = 0; i < len; ++i) a[i] = (2 * a[i] % MOD - 1ll * a[i] * a[i] % MOD * b[i] % MOD + MOD) % MOD;
NTT(a, len, 0);
for (R int i = 0; i < up; ++i) Ainv[i] = a[i];
}
IN void Dr() {for (R int i = 0; i < n; ++i) Adr[i] = 1ll * (i + 1) * A[i + 1] % MOD;}
IN void Itg() {for (R int i = 1; i < n; ++i) B[i] = 1ll * Bdr[i - 1] * fpow(i, MOD - 2) % MOD;}
IN void Getln()
{
Dr(); int len, lg;
for (len = 1, lg = 0; len < n; len <<= 1, lg++);
Getinv(len, lg + 1);
for (len = 1, lg = 0; len <= (n << 1); len <<= 1, lg++);
for (R int i = 1; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg - 1);
for (R int i = 0; i < len; ++i) a[i] = b[i] = 0;
for (R int i = 0; i < n; ++i) a[i] = Adr[i];
for (R int i = 0; i < n; ++i) b[i] = Ainv[i];
NTT(a, len, 1), NTT(b, len, 1);
for (R int i = 0; i < len; ++i) a[i] = 1ll * a[i] * b[i] % MOD;
NTT(a, len, 0);
for (R int i = 0; i < n; ++i) Bdr[i] = a[i];
Itg();
for (R int i = 0; i < n; ++i) printf("%d ", B[i]);
}
}
int main(void)
{
in(n);
for (R int i = 0; i < n; ++i) in(A[i]);
Poly::Getln();
}

最后

以上就是糟糕高山为你收集整理的[Luogu P4725] 【模板】多项式对数函数的全部内容，希望文章能够帮你解决[Luogu P4725] 【模板】多项式对数函数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。