P5265 多项式反三角函数 题解

· · 题解

arcsin

F(x)&\equiv\arcsin A(x)\pmod{x^n}\\ \\ F'(x)&\equiv(\arcsin A(x))'\pmod{x^n}\\ \end{aligned} y=\arcsin x (\arcsin x)'= \dfrac{1}{(\sin y)'}= \dfrac{1}{\cos y}= \dfrac{1}{\sqrt{1-\sin^2 y}}= \dfrac{1}{\sqrt{1-\sin^2 (\arcsin x)}}= \dfrac{1}{\sqrt{1-x^2}} F'(x)&\equiv(\arcsin A(x))'\\ \\ &\equiv\dfrac{A'(x)}{\sqrt{1-A(x)^2}}\pmod{x^n}\\ \\ F(x)&\equiv\int\dfrac{A'(x)}{\sqrt{1-A(x)^2}}\text{ d}x\pmod{x^n}\\ \end{aligned}

arctan

G(x)&\equiv\arctan A(x)\pmod{x^n}\\ \\ G'(x)&\equiv(\arctan A(x))'\pmod{x^n}\\ \end{aligned} y=\arctan x (\arctan x)'= \dfrac{1}{(\tan y)'}= \dfrac{1}{\dfrac{1}{\cos^2 y}}= \dfrac{1}{1+\tan^2 y}= \dfrac{1}{1+\tan^2 (\arctan x)}= \dfrac{1}{1+x^2} G'(x)&\equiv(\arctan A(x))'\\ \\ &\equiv\dfrac{A'(x)}{1+A(x)^2}\pmod{x^n}\\ \\ G(x)&\equiv\int\dfrac{A'(x)}{1+A(x)^2}\text{ d}x\pmod{x^n}\\ \end{aligned}

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define bceil(n) (1<<(__lg(n-1)+1))
using namespace std;
int read(){
    int a=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^'0'),ch=getchar();
    return a;
} 
void write(int a){
    if(a>9) write(a/10); 
    putchar(a%10+'0');
}
const int MAXN=1e6+10,P=998244353,G=3,Gi=332748118,Img=86583718;
int l,r[MAXN],inv[MAXN],sav[MAXN<<1];
ll qpow(ll a,ll b=P-2){
    if(a==1) return 1;
    ll ans=1;
    while(b){if(b&1) ans=ans*a%P;a=a*a%P;b>>=1;}
    return ans;
}
void tpre(int lim){
    if(l==lim) return;l=lim;
    for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)?lim>>1:0);
}
void px(int *A,int *B,int n){for(int i=0;i<n;i++) A[i]=1ll*A[i]*B[i]%P;} 
void NTT(int *A,int lim,int type){
    tpre(lim);
    static ull f[MAXN<<1],w[MAXN];w[0]=1;
    for(int i=0;i<lim;i++) f[i]=(((ll)P<<5)+A[r[i]])%P;
    for(int mid=1;mid<lim;mid<<=1){
        ull Wn=qpow(type+1?G:Gi,(P-1)/(mid+mid));
        for(int i=1;i<mid;i++)w[i]=w[i-1]*Wn%P;
        for(int j=0;j<lim;j+=mid+mid){
            for(int k=0;k<mid;k++){
                int x=w[k]*f[j|mid|k]%P;
                f[j|mid|k]=f[j|k]+P-x;
                f[j|k]+=x;
            }   
        }if(mid==(1<<10)){for(int i=0;i<lim;i++) f[i]%=P;}
    }if(type-1){
        ull inv=qpow(lim);
        for(int i=0;i<lim;i++) A[i]=f[i]%P*inv%P;
    }else for(int i=0;i<lim;i++) A[i]=f[i]%P;
}
void mul(int *A,int *B,int la,int lb){//乘法 
    int lim=bceil(la+la);
    cpy(sav,B,lim);clr(sav+la,lim-la);
    NTT(A,lim,1);NTT(sav,lim,1);
    px(A,sav,lim);NTT(A,lim,-1);
    clr(A+lb,lim-lb);clr(sav,lim);
} 
void invp(int *A,int lim){//逆元 
    int n=bceil(lim);
    static int w[MAXN<<1],r[MAXN<<1];
    w[0]=qpow(A[0]);
    for (int ln=2;ln<=n;ln<<=1){
        for(int i=0;i<(ln>>1);i++) r[i]=w[i];
        cpy(sav,A,ln);NTT(sav,ln,1);NTT(r,ln,1);px(r,sav,ln);
        NTT(r,ln,-1);clr(r,ln>>1);cpy(sav,w,ln);NTT(sav,ln,1);
        NTT(r,ln,1);px(r,sav,ln);NTT(r,ln,-1);
        for(int i=ln>>1;i<ln;i++) w[i]=(w[i]*2ll-r[i]+P)%P;
    }cpy(A,w,lim);clr(sav,n);clr(w,n);clr(r,n);
}
void rev(int *A,int lim){
    cpy(sav,A,lim);
    for (int i=0;i<lim;i++) A[i]=sav[lim-i-1];
    clr(sav,lim);
}
void mof(int *A,int *B,int n,int m){
    static int q[MAXN<<1],t[MAXN<<1],_s[MAXN]; 
    int l=n-m+1;cpy(_s,B,m);
    rev(B,m);cpy(q,B,l);rev(B,m);
    rev(A,n);cpy(t,A,l);rev(A,n);
    invp(q,l);mul(q,t,l,l);rev(q,l);
    mul(B,q,n,n);
    for(int i=0;i<m-1;i++) A[i]=(A[i]-B[i]+P)%P;
    clr(B+m-1,l);cpy(B,_s,m);clr(B+m,n-m); 
}//A<-A%B.
void dao(int *A,int lim){//导数 
    for(int i=1;i<lim;i++) A[i-1]=1ll*A[i]*i%P;
    A[lim-1]=0;
}
void inv_init(int lim){
    inv[1]=1;
    for(int i=2;i<=lim;i++) inv[i]=1ll*inv[P%i]*(P-P/i)%P;
}
void jifen(int *A,int lim){//积分 
    for(int i=lim;i;i--) A[i]=1ll*A[i-1]*inv[i]%P;
    A[0]=0;
}
void lnp(int *A,int lim){//ln 
    static int w[MAXN<<1];
    cpy(w,A,lim);
    invp(w,lim);dao(A,lim);
    mul(A,w,lim,lim);
    jifen(A,lim-1);
    clr(w,lim);
}
void exp(int *A,int lim){//exp
    static int s[MAXN<<1],s2[MAXN<<1];
    int n=bceil(lim);
    s2[0]=1;
    for(int ln=2;ln<=n;ln<<=1){
        cpy(s,s2,ln>>1);lnp(s,ln);
        for(int i=0;i<ln;i++) s[i]=(A[i]-s[i]+P)%P;
        s[0]=(s[0]+1)%P;
        mul(s2,s,ln,ln);
    }cpy(A,s2,lim);clr(s,n);clr(s2,n);
}
void sqrtp(int *A,int lim){
    int n=bceil(lim);
    static int s[MAXN<<1],s2[MAXN<<1];
    s[0]=1;
    for(int ln=2;ln<=n;ln<<=1){
        for(int i=0;i<(ln>>1);i++) s2[i]=(s[i]<<1)%P;
        invp(s2,ln);NTT(s,ln,1);px(s,s,ln);NTT(s,ln,-1);
        for(int i=0;i<ln;i++) s[i]=(A[i]+s[i])%P;
        mul(s,s2,ln,ln);
    }cpy(A,s,lim);clr(s,n+n);clr(s2,n+n);
}
void arcsin(int *A,int lim){
    static int S[MAXN];cpy(S,A,lim);dao(S,lim);
    int n=bceil(lim*2);
    NTT(A,n,1);px(A,A,n);NTT(A,n,-1);clr(A+lim,n-lim);
    for(int i=0;i<lim;i++) A[i]=(P-A[i])%P;
    A[0]=(A[0]+1)%P;sqrtp(A,lim);invp(A,lim);
    mul(A,S,lim,lim);jifen(A,lim);clr(S,lim);
}
void arctan(int *A,int lim){
    static int S[MAXN];cpy(S,A,lim);dao(S,lim);
    int n=bceil(lim*2);
    NTT(A,n,1);px(A,A,n);NTT(A,n,-1);clr(A+lim,n-lim);
    A[0]=(A[0]+1)%P;invp(A,lim);
    mul(A,S,lim,lim);jifen(A,lim);clr(S,lim);
}
int n,type,a[MAXN],b[MAXN];
int main(){
    n=read();type=read();inv_init(n);
    for(int i=0;i<n;i++) a[i]=read();
    if(type) arctan(a,n);
    else arcsin(a,n);
    for(int i=0;i<n;i++) write(a[i]),putchar(' ');
    return 0;
}