多项式开根号

引入

求出多项式是 满足 系数对一个数取模。

推导

还是利用牛顿迭代 。那么代入牛顿迭代的公式为 然后没有学习过牛顿迭代的朋友可以看我上一篇。

  • 当然这下面这份代码不能解决 的情况。那个时候应该使用二次剩余。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 4e6 + 100,P = 998244353;
int limit,r[N],L;
int ksm(int a,int b) {int x=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)x=1LL*x*a%P;return x;}
void NTT(int *a,int type) {
    for(int i=0;i<limit;i++)if(i>r[i])swap(a[i],a[r[i]]);
    for(int mid=1;mid<limit;mid<<=1) {
        int wn=ksm(3,(P-1)/(mid<<1));for(int i=0;i<limit;i+=(mid<<1)){
            for(int j=0,w=1;j<mid;j++,w=1LL*w*wn%P) {
                int x=a[i+j],y=1LL*a[i+j+mid]*w%P;
                a[i+j]=(x+y)%P;a[i+j+mid]=(x-y+P)%P;
            }
        }
    }
    if(type==-1) {reverse(a+1,a+limit);int Inv=ksm(limit,P-2);for(int i=0;i<limit;i++)a[i]=1LL*a[i]*Inv%P;}
}
void Mul(int *f,int *g,int len) {
    static int G[N];
    memcpy(G,g,sizeof(G));
    NTT(f,1);NTT(g,1);
    for(int i = 0;i < limit;i++) f[i] = 1LL * f[i] * g[i] % P;
    NTT(f,-1);for(int i=len+1;i<limit;i++) f[i]=0;
}
void init(int len) {
    limit=1;L=0;while(limit<=len)limit<<=1,L++;
    for(int i=0;i<limit;i++)r[i]=(r[i>>1]>>1)|((i&1)<<L-1);
}
void GetInv(int *f,int *g,int n) {
    if(n==1) {g[0]=ksm(f[0],P-2);return;}
    GetInv(f,g,(n+1)>>1);
    init(n+n-2);
    static int c[N];memset(c,0,sizeof(c));
    for(int i = 0;i < n;i++) c[i] = f[i];
    NTT(c,1);NTT(g,1);
    for(int i = 0;i < limit;i++) g[i] = 1LL * g[i] * ((2LL - 1LL * c[i] * g[i] % P + P) % P) % P;
    NTT(g,-1);for(int i = n;i < limit;i++) g[i] = 0;
}
void Dao(int *f,int *g,int n) {
    for(int i = 1;i < n;i++) g[i-1]=1LL*f[i]*i%P;g[n-1]=0;
}
void JiFen(int *f,int *g,int n) {
    for(int i = 1;i < n;i++) g[i]=1LL*f[i-1]*ksm(i,P-2)%P;g[0]=0; 
}
void GetLn(int *f,int *g,int n) {
    static int A[N],B[N];memset(A,0,sizeof(A));memset(B,0,sizeof(B));
    Dao(f,A,n);GetInv(f,B,n);
    init(n+n-2);NTT(A,1);NTT(B,1);
    for(int i=0;i<limit;i++)A[i]=1LL*A[i]*B[i]%P;
    NTT(A,-1);JiFen(A,g,n);
}
void GetExp(int *f,int *g,int n) {
    if(n==1) {g[0]=1;return;}
    GetExp(f,g,(n+1)>>1);static int F[N];
    memset(F,0,sizeof(F));GetLn(g,F,n);
    F[0]=(1LL*f[0]+1-F[0]+P)%P;
    for(int i=1;i<n;i++)F[i]=(-1LL*F[i]+f[i]+P)%P;
    init(n+n-2);Mul(g,F,n-1);
}
void GetPow(int *f,int *g,int n,int K) {
    static int F[N];memset(F,0,sizeof(F));
    GetLn(f,F,n);
    for(int i=0;i<n;i++)F[i]=1LL*K*F[i]%P;
    GetExp(F,g,n);
}
int inv2;
void GetSqr(int *f,int *g,int n) {
    if(n==1) {g[0]=1;return;}
    GetSqr(f,g,(n+1)>>1);static int F[N],A[N];
    memset(F,0,sizeof(F));GetInv(g,F,n);
    memset(A,0,sizeof(A));for(int i=0;i<n;i++)A[i]=f[i];
    init(n+n-2);Mul(A,F,n-1);
    for(int i=0;i<n;i++)g[i]=(1LL*g[i]+A[i])%P*inv2%P;

}
int f[N],g[N];
int main() {
    int n;inv2=ksm(2,P-2);
    cin >> n;for(int i = 0;i < n;i++) cin >> f[i];
    GetSqr(f,g,n);
    for(int i = 0;i < n;i++) cout << g[i] << " ";
    return 0;
}
数学 文章被收录于专栏

关于多项式

全部评论
orzorz
点赞 回复 分享
发布于 2020-10-16 19:26

相关推荐

不愿透露姓名的神秘牛友
07-11 12:31
以前小时候我最痛恨出轨、偷情的人,无论男女,为什么会出轨?现在我成了自己最讨厌的人,没想到分享的东西在牛客会被这么多人看,大家的评价都很中肯,我也认同,想过一一回复,但我还是收声了,我想我应该说说这件事,这件事一直压在我心里,是个很大的心结,上面说了人为什么出轨,我大概能明白了。我们大一下半年开始恋爱,开始恋爱,我给出了我铭记3年的承诺,我对她好一辈子,我永远不会背叛,我责任心太重,我觉得跟了我,我就要照顾她一辈子,我们在一起3年我都没有碰过她,她说往东我就往东,她说什么我做什么,她要我干什么,我就干什么!在学校很美好,中途也出过一些小插曲,比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了,我...
牛客刘北:两个缺爱的人是没有办法好好在一起的,但世界上哪有什么是非对错?你后悔你们在一起了,但是刚刚在一起的美好也是真的呀,因为其他人的出现,你开始想要了最开始的自己,你的确对不起自己,21岁的你望高物远,你完全可以不谈恋爱,去过你想要的生活,你向往自由,在一起之后,你要想的不是一个人,而是两个人,你不是变心了,就像你说的,你受够了,你不想包容了,冷静几天是你最优的选择,爱人先爱己。
社会教会你的第一课
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
评论
3
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务