LG4725 【模板】多项式对数函数(多项式 ln)
发布时间:2020-12-13 23:39:37 所属栏目:Linux 来源:网络整理
导读:P4725 【模板】多项式对数函数(多项式 ln) 题目描述 给出 $n-1$ 次多项式 $A(x)$,求一个 $bmod{:x^n}$ 下的多项式 $B(x)$,满足 $B(x) equiv ln A(x)$. 在 $text{mod } 998244353$ 下进行,且 $a_i in [0,998244353] cap mathbb{Z}$ 输入输出格式
P4725 【模板】多项式对数函数(多项式 ln)题目描述给出 $n-1$ 次多项式 $A(x)$,求一个 $bmod{: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_{n-1}$. 输入输出样例
输入样例#1:
复制
6 1 927384623 878326372 3882 273455637 998233543
输出样例#1:
复制
0 927384623 817976920 427326948 149643566 610586717 说明对于 $100%$ 的数据,$n le 10^5$. 题解终于理解了……多项式(mod x^n)跟整数(mod p)一样,要时刻注意取模,即保留的项数。如果项数保留过多会造成计算点值不准确。 #include<bits/stdc++.h> #define il inline #define co const template<class T>T read(){ T data=0,w=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w; for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0'; return data*w; } template<class T>il T read(T&x) {return x=read<T>();} typedef long long LL; using namespace std; typedef vector<int> polynomial; co int mod=998244353,g=3,g_inv=332748118; il int add(int a,int b){ return (a+=b)>=mod?a-mod:a; } il int mul(int a,int b){ return (LL)a*b%mod; } int fpow(int a,int b){ int ans=1; for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a); return ans; } void num_trans(polynomial&a,int inverse){ int limit=a.size(),len=log2(limit); static vector<int> bit_rev; if(bit_rev.size()!=limit){ bit_rev.resize(limit); for(int i=0;i<limit;++i) bit_rev[i]=bit_rev[i>>1]>>1|(i&1)<<(len-1); } for(int i=0;i<limit;++i)if(i<bit_rev[i]) swap(a[i],a[bit_rev[i]]); for(int step=1;step<limit;step<<=1){ int gn=fpow(inverse==1?g:g_inv,(mod-1)/(step<<1)); for(int even=0;even<limit;even+=step<<1){ int odd=even+step,gk=1; for(int k=0;k<step;++k,gk=mul(gk,gn)){ int t=mul(gk,a[odd+k]); a[odd+k]=add(a[even+k],mod-t),a[even+k]=add(a[even+k],t); } } } if(inverse==-1){ int lim_inv=fpow(limit,mod-2); for(int i=0;i<limit;++i) a[i]=mul(a[i],lim_inv); } } polynomial poly_inv(polynomial a,int n){ // mod x^n polynomial b[2]; b[0].push_back(fpow(a[0],mod-2)); if(n==1) return b[0]; a.resize(1<<int(ceil(log2(n))+1)); int limit,len; for(limit=2,len=1;limit<n;limit<<=1,++len){ polynomial a1(a.begin(),a.begin()+limit); a1.resize(limit<<1),num_trans(a1,1); b[(len&1)^1].resize(limit<<1),num_trans(b[(len&1)^1],1); b[len&1].resize(limit<<1); for(int i=0;i<limit<<1;++i) b[len&1][i]=mul(add(2,mod-mul(a1[i],b[(len&1)^1][i])),b[(len&1)^1][i]); num_trans(b[len&1],-1),b[len&1].resize(limit); } assert(a.size()==limit<<1),num_trans(a,1); b[(len&1)^1].resize(limit<<1),1); b[len&1].resize(limit<<1); for(int i=0;i<limit<<1;++i) b[len&1][i]=mul(add(2,mod-mul(a[i],b[(len&1)^1][i]); num_trans(b[len&1],b[len&1].resize(n); return b[len&1]; } polynomial poly_der(co polynomial&a){ polynomial b(a.size()-1); for(int i=0;i<b.size();++i) b[i]=mul(i+1,a[i+1]); return b; } polynomial poly_int(co polynomial&a){ polynomial b(a.size()+1); for(int i=1;i<b.size();++i) b[i]=mul(fpow(i,mod-2),a[i-1]); return b; } polynomial poly_ln(polynomial a,int n){ // mod x^n polynomial b=poly_inv(a,n); a=poly_der(a); int limit=1<<int(ceil(log2(2*n-1))); a.resize(limit),b.resize(limit); num_trans(a,1),num_trans(b,1); for(int i=0;i<limit;++i) a[i]=mul(a[i],b[i]); num_trans(a,a.resize(n); a=poly_int(a),a.resize(n); return a; } int main(){ int n=read<int>(); polynomial a(n); for(int i=0;i<n;++i) read(a[i]); polynomial b=poly_ln(a,n); for(int i=0;i<n;++i) printf("%d ",b[i]); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |