题解：P5265 多项式反三角函数

xzh1 · 2026-04-28 13:48:29 · 题解

题解

考虑像求多项式 \ln 一样，将 \arcsin A(x) 求导再积分。

先求出 \arcsin x 的导数。\arcsin x 是 \sin x 的反函数，令 y=\arcsin x，则 x=\sin y。\frac{dx}{dy}=\cos y=\sqrt{1-\sin^2 y}=\sqrt{1-x^2}，所以 \arcsin x 的导数为 \frac{1}{\sqrt{1-x^2}}，同理容易推出 \arctan x 的导数为 \frac{1}{1+x^2}。

所以当 type=0 时，F(x)=\int \frac{A'(x)}{\sqrt{1-A^2(x)}}dx。

当 type=1 时，F(x)=\int \frac{A'(x)}{1+A^2(x)}dx。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=5e5+5,mod=998244353;
int n,opt,A[N],tA[N],B[N],tB[N],c[N],d[N],r[N],ans[N],lim,inv;

int qpow(int a,int b,int res=1){
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}

void init(int nn){
    lim=1;
    while(lim<(nn<<1)) lim<<=1;inv=qpow(lim,mod-2);
    for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
    return;
}

void NTT(int *a,int limit,bool type){
    for(int i=0;i<limit;i++)
        if(r[i]>i) swap(a[i],a[r[i]]);
    for(int k=1;k<limit;k<<=1){
        int gn=qpow(3,(mod-1)/(k<<1));
        if(!type) gn=qpow(gn,mod-2);
        for(int i=0;i<limit;i+=(k<<1))
            for(int j=0,G=1;j<k;j++,G=G*gn%mod){
                int x=a[i+j+k]*G%mod,y=a[i+j];
                a[i+j+k]=(y-x+mod)%mod;
                a[i+j]=(x+y)%mod;
            }
    }
    return;
}//NTT

void Der(int *a,int *b,int nn){
    for(int i=0;i<nn;i++) b[i]=a[i+1]*(i+1)%mod;
    return;
}//求导

void Calc(int *a,int *b,int nn){
    b[0]=0;
    for(int i=1;i<=nn;i++) b[i]=a[i-1]*qpow(i,mod-2)%mod;
    return;
}//积分

void Mul(int *a,int *b,int nn){
    init(nn),copy(a,a+nn,c),fill(c+nn,c+lim,0),NTT(b,lim,1),NTT(c,lim,1);
    for(int i=0;i<lim;i++) b[i]=b[i]*c[i]%mod;
    NTT(b,lim,0),fill(b+nn,b+lim,0);
    for(int i=0;i<lim;i++) b[i]=b[i]*inv%mod;
    return;
}//多项式乘法

void Inv(int *a,int *b,int nn){
    if(nn==1) return b[0]=qpow(a[0],mod-2),void();
    Inv(a,b,(nn+1)>>1),init(nn),copy(a,a+nn,c),fill(c+nn,c+lim,0),NTT(b,lim,1),NTT(c,lim,1);
    for(int i=0;i<lim;i++) b[i]=(2-b[i]*c[i]%mod+mod)%mod*b[i]%mod;
    NTT(b,lim,0),fill(b+nn,b+lim,0);
    for(int i=0;i<lim;i++) b[i]=b[i]*inv%mod;
    return;
}//多项式乘法逆

void Sqrt(int *a,int *b,int nn){
    if(nn==1) return b[0]=1,void();
    Sqrt(a,b,(nn+1)>>1),fill(d,d+N,0),Inv(b,d,nn);
    copy(a,a+nn,c),fill(c+nn,c+lim,0),init(nn),Mul(c,d,nn);
    for(int i=0;i<lim;i++) b[i]=(b[i]+d[i])%mod*qpow(2,mod-2)%mod;
    return;
}//多项式开根

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> opt;
    for(int i=0;i<n;i++) cin >> A[i];
    Der(A,tA,n),Mul(A,A,n);
    if(!opt){
        A[0]=(1-A[0]+mod)%mod;
        for(int i=1;i<n;i++) A[i]=(mod-A[i])%mod;
        Sqrt(A,B,n),Inv(B,tB,n),Mul(tB,tA,n),Calc(tA,ans,n);
        for(int i=0;i<n;i++) cout << ans[i] <<" ";
    }else{
        A[0]=(1+A[0])%mod;
        Inv(A,B,n),Mul(B,tA,n),Calc(tA,ans,n);
        for(int i=0;i<n;i++) cout << ans[i] <<" ";
    }
    return 0;
}