多项式乘法
多项式全家桶的前置知识肯定就是多项式乘法了啊, 放个板子
struct NTT {
ll wn[2][maxn],tmp1[maxn],tmp2[maxn];
int rev[maxn];
void get_wn(int len) {
for(int i=2;i<=(1<<len);i<<=1) {
ll w1=ksm(3,(mod-1)/i),w0=ksm(3,mod-1-(mod-1)/i);
wn[1][i>>1]=wn[0][i>>1]=1;
for(int j=1;j<(i>>1);j++) {
wn[0][(i>>1)+j]=w0*wn[0][(i>>1)+j-1]%mod;
wn[1][(i>>1)+j]=w1*wn[1][(i>>1)+j-1]%mod;
}
}
}
NTT(){
int cnt=0,len=1,top=2e5+10;while(len<=top)len<<=1,cnt++;
get_wn(cnt);
}
void ntt(int len,ll *c,int f){
for(int i=0;i<len;i++)if(rev[i]>i)swap(c[i],c[rev[i]]);
for(int l=2;l<=len;l<<=1) {
for(int i=0;i+l<=len;i+=l) {
for(int j=i;j<i+(l>>1);j++) {
ll tmpa=c[j],tmpb=c[j+(l>>1)]*wn[f][j+(l>>1)-i]%mod;
c[j]=tmpa+tmpb;c[j]%=mod;
c[j+(l>>1)]=tmpa-tmpb;c[j+(l>>1)]=(c[j+(l>>1)]%mod+mod)%mod;
}
}
}
if(!f) {
ll inv=ksm(len,mod-2);
for(int i=0;i<len;i++)c[i]=c[i]*inv%mod;
}
}
void get_rev(int len){rep(i,1,1<<len)rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));}
vi mul1(const vi &a,const vi &b) {//普通多项式乘法
int l1=a.size(),l2=b.size(),len=1,cnt=0;while(len<=l1+l2)len<<=1,cnt++;
get_rev(cnt);rep(i,0,len)tmp1[i]=tmp2[i]=0;
rep(i,0,l1-1)tmp1[i]=a[i];
rep(i,0,l2-1)tmp2[i]=b[i];
ntt(len,tmp1,1);ntt(len,tmp2,1);
rep(i,0,len-1)tmp1[i]=tmp1[i]*tmp2[i]%mod;
ntt(len,tmp1,0);vi re;re.clear();
rep(i,0,len-1)re.pb(tmp1[i]);
re.resize(l1+l2);
return re;
}
}t;
多项式求逆
在多项式运算中,很多时候需要用到除法,那么多项式求逆就是必不可少的了。
多项式求逆,其实就是要解决的问题,其中已知,且。
为什么需要保证?
之所以需要保证,是因为多项式对取模实际上就是舍掉多项式大于等于次的项。所以如果常数项为0,那么不管模数是多少,都不可能使取模后的常数项为1,所以无解
如何求逆?
推柿子
首先我们发现,如果找出了使得
那么显然有,因为现在的模数是原来模数的因子。
因此
然后:
因此这个多项式后项均为0,然后这个柿子平方一下就是:
(因为平方之后后n项均为0)
我们想得到B和B'的关系柿,那么就随便搞搞:
然后就没了 写一个递归多项式乘法就好了。实现上有个小技巧 ,就是多项式乘法这里有一个二次的。我们可以直接在转换为点值表示之后的乘法里下功夫,具体看代码吧。
代码实现的时候需要注意一个比较严重的问题 就是这个多项式中有一个,所以我们在NTT初始化计算长度的时候的时候要注意长度需要给到也就是当前层的。
多项式对数函数(多项式ln)
多项式对数函数,其实就是要解决的问题,其中已知,且。
为什么需要保证?
因为众所周知,对数函数的函数图像定点是。
如何求对数函数?
推柿子
我们把对数函数设成,则有
由微积分里面的链式法则,两边求一下导,就有了
我们知道对数函数的导函数是,那么就有
上面的分子利用多项式求导能很方便的求出来:,如果带了系数的话,那,这个可以用链式法则解释。
下面的部分多项式求个逆序也很简单。
然后我们就得到了这个多项式,接着不定积分一波就没了。
多项式指数函数(多项式exp)
前置知识
泰勒展开
我们发现,对于一个多项式求导,会使其丢失常数项的信息。
有一句话说得很好:原函数的信息 = 导函数的信息 + 初始值信息
具体的引入有一篇知乎答案 怎样更好地理解并记忆泰勒展开式?这里就不细说了。
总的来说 就是把一个多项式展开成无穷级数的样子。
最后推导出来的公式就是:,其中代表函数的阶导,为我们选择的展开点。
牛顿迭代
已知,给出,求出。其实就是求这个函数的零点。
大体的思路就是求在模一个很小的数意义下的,然后逆用泰勒展开 看看如何转换才能使模数变大。
我们令表示经过 t 次迭代之后的 ,满足。
考虑将 $G[F_{t+1}(x)] F_t(x) $处展开:
因为的时候,的次数是大于等于的,而且这两项在意义下都是0,所以差也是0,差的平方就会在意义下变成0。
所以后面那一坨一定是0,来看前面的部分,就有
然后有:
就没啦~~~
如何求指数函数?
多项式指数函数,其实就是要解决的问题,其中已知,且保证。
我们令。需要注意的是 这个柿子里面这个多项式是自变量,这个多项式是常数。(看起来很玄学 其实是蛮有道理的,很多多项式算法都是把一个多项式当作一个变量来看待,也就是形式幂级数)。
然后牛顿迭代一波:
在最底层的时候,模数是,因此零点就是。(,所以,这也是为什么需要保证)
就没啦~~~
P.S. 在实际写代码的时候,对于模数可以向下递归,不停的除二且向上取整就行。因为你只要保证前一次的模数平方之后是大于现在的模数的就行了。
多项式全家桶代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=2e5*4+1000;
const int mod=998244353;
int ksm(ll num,ll t) {
int res=1;
for(;t;t>>=1,num=1ll*num*num%mod) {
if(t&1)res=1ll*res*num%mod;
}
return res%mod;
}
struct NTT {
ll wn[2][maxn],tmp1[maxn],tmp2[maxn];
int rev[maxn];
void get_wn(int len) {
for(int i=2;i<=(1<<len);i<<=1) {
ll w1=ksm(3,(mod-1)/i),w0=ksm(3,mod-1-(mod-1)/i);
wn[1][i>>1]=wn[0][i>>1]=1;
for(int j=1;j<(i>>1);j++) {
wn[0][(i>>1)+j]=w0*wn[0][(i>>1)+j-1]%mod;
wn[1][(i>>1)+j]=w1*wn[1][(i>>1)+j-1]%mod;
}
}
}
NTT(){
int cnt=0,len=1,top=maxn/2-100;while(len<=top)len<<=1,cnt++;
get_wn(cnt);
}
void ntt(int len,ll *c,int f){
for(int i=0;i<len;i++)if(rev[i]>i)swap(c[i],c[rev[i]]);
for(int l=2;l<=len;l<<=1) {
for(int i=0;i+l<=len;i+=l) {
for(int j=i;j<i+(l>>1);j++) {
ll tmpa=c[j],tmpb=c[j+(l>>1)]*wn[f][j+(l>>1)-i]%mod;
c[j]=tmpa+tmpb;c[j]%=mod;
c[j+(l>>1)]=tmpa-tmpb;c[j+(l>>1)]=(c[j+(l>>1)]%mod+mod)%mod;
}
}
}
if(!f) {
ll inv=ksm(len,mod-2);
for(int i=0;i<len;i++)c[i]=c[i]*inv%mod;
}
}
void get_rev(int len){rep(i,1,1<<len)rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));}
vi mul1(const vi &a,const vi &b,const int &mx) {//普通多项式乘法
int l1=a.size(),l2=b.size(),len=1,cnt=0;l1=min(l1,mx),l2=min(l2,mx);while(len<=l1+l2)len<<=1,cnt++;
get_rev(cnt);rep(i,0,len)tmp1[i]=tmp2[i]=0;
rep(i,0,l1-1)tmp1[i]=a[i];
rep(i,0,l2-1)tmp2[i]=b[i];
ntt(len,tmp1,1);ntt(len,tmp2,1);
rep(i,0,len-1)tmp1[i]=tmp1[i]*tmp2[i]%mod;
ntt(len,tmp1,0);vi re;re.clear();
rep(i,0,len-1)re.pb(tmp1[i]);
re.resize(mx);
return re;
}
vi mul2(const vi &a,const vi &b,const int &mx) {//多项式求逆用到的多项式乘法(唯一的不同是点值)
int l1=a.size(),l2=b.size(),len=1,cnt=0;l1=min(l1,mx),l2=min(l2,mx);while(len<=l1+l2)len<<=1,cnt++;
get_rev(cnt);rep(i,0,len)tmp1[i]=tmp2[i]=0;
rep(i,0,l1-1)tmp1[i]=a[i];
rep(i,0,l2-1)tmp2[i]=b[i];
ntt(len,tmp1,1);ntt(len,tmp2,1);
rep(i,0,len-1)tmp1[i]=((tmp2[i]*2-tmp2[i]*tmp2[i]%mod*tmp1[i]%mod)%mod+mod)%mod;
ntt(len,tmp1,0);vi re;re.clear();
rep(i,0,len-1)re.pb(tmp1[i]);
re.resize(mx);
return re;
}
}t;
vi get_inv(const vi &a,int n){
if(n==1){vi re;re.clear();re.pb(ksm(a[0],mod-2));return re;}
vi b_=get_inv(a,(n+1)>>1);b_.resize(n);vi a_=a;a_.resize(n);
return t.mul2(a_,b_,n);
}
vi der(vi a) {//多项式求导
for(int i=1;i<a.size();i++)a[i-1]=1ll*a[i]*i%mod;
a.resize(a.size()-1);
return a;
}
vi inte(vi a) {//多项式积分
a.resize(a.size()+1);
for(int i=a.size()-1;i>0;i--)a[i]=(1ll*a[i-1]*ksm(i,mod-2)%mod)%mod;
a[0]=0;
return a;
}
vi ln(const vi &a,int n) {
vi u=der(a),d=get_inv(a,n);
vi bder=t.mul1(u,d,n);
vi ans=inte(bder);ans.resize(n);
return ans;
}
vi exp(const vi &a,int n) {
if(n==1){vi re;re.pb(1);return re;}
vi last=exp(a,(n+1)>>1);
vi ln_=ln(last,n);
for(int i=0;i<n;i++)ln_[i]=((a[i]-ln_[i])%mod+mod)%mod;
ln_[0]++;
ln_=t.mul1(ln_,last,n);
return ln_;
}
int main(){
int n;scanf("%d",&n);
vi a;rep(i,1,n){int u;scanf("%d",&u);a.pb(u);}
a=exp(a,n);
rep(i,1,n){printf("%d ",a[i-1]);}
return 0;
}