Warning: session_start(): open(/tmp/sess_85d63996bb25f5865fda9f664fd8c5a4, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====问题描述====
给定一个n-1次多项式$f(x)$，保证$a_0=1$。求$\ln(f(x))$对$x^n$取模的结果。系数模998244353
$\ln(f(x))$定义为其幂级数展开，对$x^n$取模为其幂级数的前n项和。
====解决方法====
===前置知识===
多项式乘法（NTT），多项式求逆，多项式求导、积分（这个所有人都会）
===正文===
设$g(x)=\ln(f(x))$，则$g'(x)\equiv\frac{f'(x)}{f(x)}\equiv f'(x)f^{-1}(x)\pmod{x^n}$。
由多项式求逆算得$f^{-1}(x)$（对$x^n$取模），求导得到$f'(x)$，然后NTT算得$f'(x)f^{-1}(x)$，这就是$g'(x)$对$x^n$取模的结果。
最后再积分得到$g(x)$即可。显然，g(x)的常数项应该是0
====问题分析====
时间复杂度O($n\log n$)，空间复杂度O(n)
模板：洛谷4725
#include
#include
#include
#define N 200005
#define LL long long
using namespace std;
const LL mod=998244353;
int n,m;
int rank[N<<1];
LL f1[N<<1],f2[N<<1];
LL ksm(LL x,LL y)
{
LL res=1;
while(y)
{
if(y&1) res=res*x%mod;
y>>=1;
x=x*x%mod;
}
return res;
}
void ntt(LL *a,int type)
{
int i,j,k;
for(i=0;i0)?ksm(3,(mod-1)/(i<<1)):ksm((mod+1)/3,(mod-1)/(i<<1));
for(j=0;j>1)>=l)
{
n=1;
while((1<>1]>>1)|((i&1)<